[Algorithm] [Python & Swift] 백준/BOJ - 2178 _ 미로 탐색

2178 - 미로 탐색

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

제출 코드

---

 

Python

from sys import stdin
from collections import deque

def boundaryCheck(x, y):
    return True if 0 <= x < n and 0 <= y < m else False

n, m = map(int, stdin.readline().split())
matrix = [list(map(int, stdin.readline().strip())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

queue = deque([0, 0])
visited[0][0] = 1

while queue:
    x,y = queue.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if boundaryCheck(nx, ny) and visited[nx][ny] == 0 and matrix[nx][ny] == 1:
            matrix[nx][ny] = matrix[x][y] + 1
            queue.append([nx, ny])

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

 

Swift

import Foundation

func boundaryCheck(_ x: Int, _ y: Int) -> Bool {
    return (0 <= x && x < n && 0 <= y && y < m) ? true : false
}

let input = readLine()!.split(" ").map { Int($0)! }
let n = input[0], m = input[1]
let dx = [1, -1, 0, 0], dy = [0, 0, -1, 1]
var matrix = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
var visited = matrix
var queue = [(Int, Int)]()               // (Int, Int) 튜플 타입을 원소로 갖는 배열로 2차원 배열 대체

for i in 0..<n {
    matrix[i] = readLine()!.map { Int(String($0))! }
}

visited[0][0] = 1
queue.append((0, 0))

while !queue.isEmpty {
    let (x,y) = queue.removeFirst()

    for i in 0..<4 {
        let nx = x+dx[i]
        let ny = y+dy[i]

        if boundaryCheck(nx, ny) && visited[nx][ny] == 0 && matrix[nx][ny] == 1 {
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))
        }
    }
}

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

 

코드 설명

---

BFS 개념을 이용하여 문제를 풀었다.

1. 시작점에서 부터 동, 서, 남, 북 이동 가능 여부를 파악한다.
2. 이동이 가능한 경우, 해당 위치로 이동하며 queue에 해당 위치를 넣고 몇번째 방문 위치인지 카운트 값을 기록한다.
3. queue가 빌 떄 까지, 즉 동, 서, 남, 북 모두 이미 방문했거나 접근이 불가한 경우 까지 반복한다.

도착점에 기록된 카운트 값을 출력한다.