[Swift Algorithm] 미로 탐색 BOJ #2178

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

입출력 예제

입력

4 6
101111
101010
101011
111011

출력

15

 

내 문제 풀이

import Foundation

let size = readLine()!.split(separator: " ").map({Int(String($0))!})
let n = size[0] // 세로 길이
let m = size[1] // 가로 길이
var maze = [[Int]]() // 미로
var queue = [(0, 0)] // 경로의 좌표 값을 담을 큐
let dx = [-1, 1, 0 , 0], dy = [0, 0, -1, 1] // 상하좌우 검색을 위한 좌표 변화량

for _ in 0..<n {
    maze.append(readLine()!.map({Int(String($0))!}))
}

// 큐가 빌 때까지 반복
while !queue.isEmpty {
    let (x, y) = queue.removeFirst() // FIFO로 큐의 첫 번째 pop
    
    // 상, 하, 좌, 우 검색을 위해 0부터 3까지 총 4번 반복
    for i in 0..<4 {
        // 현재 위치에 x, y축 각각 dx[i], dy[i] 값을 더해서 검색할 좌표 구해주기
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        // nx, ny가 주어진 미로의 크기에 벗어나거나, 검색할 자리가 0일 경우 continue
        if nx < 0 || ny < 0 || nx >= n || ny >= m || maze[nx][ny] == 0 { continue }
        
        // 검색할 자리가 1일 경우
        if maze[nx][ny] == 1 {
            maze[nx][ny] = maze[x][y] + 1 // 검색하는 자리에 현재 자리에서 1 더한 값 누적
            queue.append((nx, ny)) // 큐에 nx, ny 값 추가
        }
    }
}

print(maze[n-1][m-1])

👉 1로 이어진 모든 경로를 탐색하는 것이 포인트!

이어진 자리들을 체크해주어야 한다는 점에서 이전에 풀었던 #1926_그림문제와 비슷하다.

• 1이 채워진 모든 경로로 한 칸씩 나아가면서, 목적지까지의 길이를 구하는 문제이다.
  따라서 어디까지 경로를 탐색했는지 업데이트해줄 수 있는 큐가 필요하다.
  queue라는 이름으로 배열을 생성하고, (0, 0)부터 탐색할 예정이므로 (0, 0)을 먼저 저장했다.
  그리고 상하좌우 모든 경로를 고려해줘야하므로, dx, dy 배열로 좌표 변화량을 표현해주었다.
• while을 사용해서 더이상 탐색할 경로가 없어질 때까지 반복했다.
  우선 queue에 가장 먼저 저장됐던 값을 꺼내서 x, y에 저장해주었다.
  그리고 상하좌우를 모두 검사하기 위해 for문으로 딱 4번 반복하게 했다.
  nx, ny 상수를 각각 x, y에 알맞는 좌표값을 더해서 정의했다.
  이 때 혹시 nx나 ny가 미로의 크기를 벗어나거나 0이 할당된 자리일 경우는 예외처리했다.
  검색할 자리에 1이 할당되어있을 경우, 1을 누적해준다. ((0, 0)부터 (nx, ny)까지의 거리를 의미!)
  그리고 queue에 (nx, ny)를 append해줌으로써 다음에 검사할 경로를 추가한다.

 

💡 피드백

• 전형적인 BFS문제같은데, 1로 이어지는 모든 경로의 길이를 구해주어야했다.
  '최소'길이를 구해줘야한다는 말에 사로잡혀서 처음엔 복잡하게 풀이를 하려다 실패했는데
  그냥 BFS답게 모든 경로를 탐색하면 되는것,,!
• 계속 문제를 많이 풀어봐야겠당.

 

---

 

문제

https://www.acmicpc.net/problem/2178