BOJ-2187 미로 탐색 Swift

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

내가 푼 풀이

- 주어진 배열 N x M에서 (1, 1)에서 (N, M)까지 이동하는 최소 칸 수를 구하면 된다.

- dp로 풀 수 있을꺼같지만, BFS를 이용해서 풀었다.

- 주어진 인덱스와 인접한 4방향 위치 중에 1인값들을 저장했다.

- maze[[Int]: [[Int]]] = key는 x, y값이고 value는 인접한 위치 중 이동할 수 있는 위치의 인덱스 x, y 들로 구성되었다.

- x =1, y = 1 부터 시작해서 인접한 위치를 탐색하며, 그 위치 중 이미 방문했던 곳이 있다면, 그곳까지의 칸수 + 1을 하는 방법을 사용했다.

 

위에 예시로 주어진 배열을 이용해서 예로들어본다.

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

 

네 방향으로 인접한 위치 중 방문할 수 있는 위치인지 파악하기 위해 (N+2) * (M+2) 크기로 만들어준다.

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

그리고 해당 위치까지 이동했을 때, 이동한 칸수의 최솟값을 저장할 배열 하나를 같은 크기로 만들어주고, [1,1]에 1을 저장.

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

인접한 인덱스 중 방문할 수 있는 위치를 리스트로 만든다.

[1,1]은 [2,1]과 인접하고, [2,1]은 [1,1]과 [3,1]이 인접한다.

[1,1]: [2,1]

[2,1]: [1,1], [3,1]

 

BFS를 이용해 1,1 이 인접한 위치로 이동하며, 이동한 위치 [2,1]에서 인접한 위치 [1,1], [3,1] 중 이미 방문했던 위치가 있다면,

그 위치 [1,1] 값 +1을 해준다.

그러면 결과배열에 다음과 같이 저장된다.

0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0
0	2	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

위 방법을 통해 방문할 수 있는 모든 위치를 지나게 된다면, 결과 배열은 다음과 같이 저장된다.

 

0	0	0	0	0	0	0	0
0	1	0	9	10	11	12	0
0	2	0	8	0	12	0	0
0	3	0	7	0	13	14	0
0	4	5	6	0	14	15	0
0	0	0	0	0	0	0	0

 

마지막 m, n 위치의 값을 출력하면 된다.

해당 알고리즘을 코드로 구현하면 다음과 같다.

 

import Foundation

// 결과배열 result
// 인접된 인덱스리스트 maze
var index = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: index[1]+2)]
var maze = [[Int]: [[Int]]]()
var result = Array(repeating: Array(repeating: 0, count: index[1]+2), count: index[0]+2)
result[1][1] = 1

// (N+2) * (M+2) 크기의 배열 만들기
for i in 0..<index[0] {
    var nums = Array(readLine()!).map{ Int(String($0))!}
    arr.append([0] + nums + [0])
}
arr.append(Array(repeating: 0, count: index[1]+2))

// 인접리스트 maze 입력하기
for i in 1...index[0] {
    for j in 1...index[1] {
        if arr[i][j] == 1 {
            if arr[i-1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i-1,j]]
                } else {
                    maze[[i,j]]!.append([i-1,j])
                }
            }
            if arr[i][j-1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j-1]]
                } else {
                    maze[[i,j]]!.append([i,j-1])
                }
            }
            if arr[i+1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i+1,j]]
                } else {
                    maze[[i,j]]!.append([i+1,j])
                }
            }
            if arr[i][j+1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j+1]]
                } else {
                    maze[[i,j]]!.append([i,j+1])
                }
            }
        }
    }
}

// 방문한 위치 배열
// 방문해야 할 위치 배열
var visitedQueue = [[Int]]()
var needVisitQueue = [[1,1]]

// BFS
while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeFirst()
    
    if visitedQueue.contains(node) { continue }
    visitedQueue.append(node)
    needVisitQueue += maze[node]!
    // 해당 위치가 시작지점이면 패스
    // 해당위치 이전의 방문한 위치가 있다면 그 위치의값 + 1
    if node == [1,1] {
        continue
    } else {
        for i in maze[node]! {
            if visitedQueue.contains(i) {
                result[node[0]][node[1]] += result[i[0]][i[1]] + 1
                break
            }
        }
    }
}

print(result[index[0]][index[1]])