Backtracking백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.가장 중요한 점은 제한 조건을 위배한다면 그 노드를 제외한다는 점이다,.현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다.DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요 없는 부분을 쳐내는 행위를 백트래킹(가지치기)이라고 생각하면 된다.DFS와 Backtracking의 다른점DFS..

⭐️ DFS (Depth First Search)정해진 규칙에 의해 시작 정점에서 멀어지는 방향 우선으로 탐색하는 방법일반적으로 재귀함수를 사용해서 구현한다. (Stack으로도 구현 가능하지만, 구현이 상당히 복잡해진다.)그래프가 트리 형태일 때, DFS 알고리즘이 자주 쓰인다.최단거리를 구하기에는 적합한 알고리즘이 아니다. (시간 초과 주의)재귀로 구현된다는 점에서 Backtracking 과 유사하다.📝 DFS (Depth First Search) 탐색 구현 방법방문 체크 용 (재방문 방지) 배열을 만든다.현재 정점을 파라미터로 넘겨 받는 함수(메소드)를 정의한다.함수(메소드) 내부에서..현재 정점이 이미 방문한 정점이면 return 한다.현재 정점의 방문 체크를 한다.해당 정점에서 방문 가능한 다음..

📝 문제https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr[설명]n x m 크기의 게임 맵 시작 지점에서, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 최소 칸의 개수 구하기단, 상대 팀 진영에 도착할 수 없을 때는 -1 리턴 [접근 방법]BFS(너비 우선 탐색) 활용 [주의 사항]BFS 활용법 외우면 풀기 수월하다.방문처리는 큐에 넣을 때 꼭 같이 해줘야한다.참고 : https://school.programmers.co.kr/questions/38232 🔑 풀이import java..

Graph일반적으로 그래프에서 정점의 표현은 v (Vertex), 간선의 표현은 E (Edge)로 한다.바둑판 형태의 맵에서 탐색하는 것 또한 각 칸을 정점, 다른 칸으로 이동 가능한 방법을 간선으로 볼 수 있다.일반적인 문제에선 정점과 간선의 조합으로 문제가 많이 나오기 떄문에 그패의 정보를 저장할 떄 인접리스트를 많이 사용하게 되지만, 기업 입사 코딩테스트에서는 바둑판 형태의 그래프가 더 자주 나온다.상하좌우로 이동 가능할 경우 간선은?기본적으로 1칸당 4개의 간선이 있는 것으로 생각범위 밖으로 나가는 경우에 대해서는 예외처리인접 리스트그래프의 정보는 코딩테스트에서 어떻게 주어지고, 어떻게 저장을 해야 탐색에 유리할까?일반적으로 그래프의 정보는 아래와 같이 주어진다. [A, B] : A에서 B로 이동..