섹션 8. DFS, BFS 활용 11. 미로의 최단거리 통로(BFS)

문제

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

입력

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

출력

• 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 
• 도착할 수 없으면 -1을 출력한다.

입출력 예제

---

풀이방식

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

 

---

설계과정

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

2. 큐를 선언하고, 큐에 미리 선언한 Point 객체 값을 넣는다.

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

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

5. 큐에 현재 좌표 값을 넣고 dis 배열에 좌표값에 1을 더한 값을 넣는다.

6. 통로 끝까지 왔을 때에 값이 0이라면 -1을 출력하고, 아니라면 해당 값을 출력한다.

---

풀이과정

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

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

2. 큐를 생성하고 큐에 포인트 객체 값을 넣어준다.

• 미리 생성한 Point 객체를 말하며, 이는 현재의 x, y 좌표값을 의미한다.

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

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

4. Q.poll() 을 통해 큐에서 좌표값을 빼서 nx와 ny에 각각 dx[ ], dy[ ] 배열 값들을 더하는 for문을 돌린다

• tmp에 큐에서 꺼낸 현재 x,y 좌표값을 넣고 그 값에 각각 dx[ ], dy[ ] 값을 더해서 상하좌우 이동 좌표 값을 구한다.

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

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

6. 큐에 현재의 좌표 값을 넣어서 새 객체 값을 넣어준다.

 

7. dis[nx][ny] 에 현재의 x,y 좌표값을 넣은 후 1을 더해서 저장한다.

• dx[ ], dy[ ] 배열을 통해 상하좌우로 이동한 좌표에 방문한다는 의미이기에 1을 더해준다.

8. dis[7][7] 배열 값이 0이라면 -1을 리턴한다.

• 맨 마지막 좌표가 0이라면 방문하지 못했음을 의미하므로 -1을 출력한다.

9. 0이 아니라면 dis[7][7] 값을 리턴한다.

• 배열의 맨 마지막 값이 결국 거리를 의미하기 때문이다.

---

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

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

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

---

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