섹션 8. DFS, BFS 활용 10. 미로탐색(DFS)

문제

• 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.
• 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.
• 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

• 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입력

• 7*7 격자판의 정보가 주어집니다.

출력

• 첫 번째 줄에 결과를 출력합니다. 
• 출력 순서는 사전 순으로 오름차순으로 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

1. 이동 방향을 담은 배열 dy, dx에 값을 넣어서 저장한다.

2. 출발점은 무조건 방문하므로 1을 넣는다.

3. 경계선 안쪽이고 통로라면 지나갈 수 있는 곳이므로 board 배열에 1을 넣어서 방문기록을 남긴다.

4. 재귀함수 DFS를 호출한다.

5. 이 때 DFS의 파라미터는 nx, ny를 넣어준다.

6. nx는 x + dx[i], ny는 y + dy[i] 를 넣은 값이다.

7. 통로 끝까지 왔다면 result 변수에 1씩 더하여 결과를 누적한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 행의 이동 좌표를 위한 배열 dx[ ] 을 선언한다.
• 열의 이동 좌표를 위한 배열 dy[ ] 을 선언한다.
• 방문 기록을 저장할 배열 board[ ] 을 선언한다.
  • 이 때, 인덱스가 1부터 시작하도록 하기 위해 크기를 8로 선언한다.
• 현재 좌표에서 이동할 수 있는 방향을 알기 위해 nx, ny를 선언해서 dx[ ], dy[ ] 배열의 값을 각각 더해준다.

2. 출발점은 무조건 방문하므로 board 배열에 1을 넣어준다.

• 1은 방문 했음을 의미하는 값이고, 0은 방문하지 않음을 의미하는 값이다.

3. nx와 ny에 각각 dx[ ], dy[ ] 배열 값들을 더하는 for문을 돌린다.

• 행, 열 좌표에 각각 상하좌우 이동 좌표를 구하기 위한 과정이다.

4. 행과 열을 기준으로 경계선 안쪽이고 이동 가능한 통로라면 board[nx][ny]에 1을 넣어준 후 재귀함수를 호출한다.

• nx >= 1 && nx <= 7 : 행을 기준으로 경계선 안쪽임을 의미한다.
• ny >= 1 && ny <= 7 : 열을 기준으로 경계선 안쪽임을 의미한다.
• board[nx][ny] == 0 : 통로임을 의미한다.

5. 통로의 끝에 도달했으면 결과에 1을 더해준다.

 

6. DFS(1, 1) 으로 재귀함수를 시작하며 결과를 확인한다.

 

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.