[BFS / 중급] 미로 탐색 (백준, Python, 실버1)

문제

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

출력

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

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

풀이

풀이과정

위 그림들처럼 테스트케이스별로 그려가며 문제를 파악했다.

1. q를 돌린다.
   1. map에서 현 위치에서 상하좌우 갈 수 있는 지점을 찾는다. (이미 방문한 길 아니면서 벽이 아닌 경우)
   2. 해당 지점에 현재 depth를 저장한다.
   3. target에 도착하면 최종 depth를 반환한다.

# import sys
# input = sys.stdin.readline

n, m = map(int, input().split())

riddle = [[int(i) for i in str(input())] for _ in range(n)]

from collections import deque
def bfs(riddle):
    base = 0    # 앞으로 이전 좌표?값?을 저장할 변수
    wasd = [[1,0], [-1,0], [0,1], [0,-1]]   # 갈 수 있는 경로
    visited = [[False]*m for _ in range(n)] # 방문한 곳 저장

    q = deque() # 앞으로 갈 수 있는 곳 저장
    q.append([0,0])
    visited[0][0] = True

    # print(visited[0][0])
    while q:
        item = q.popleft()
        base = riddle[item[0]][item[1]] # 이전 좌표 값
        # print(item)
        for w in wasd:
            if item[0]+w[0] == (n-1) and item[1]+w[1] == (m-1):
                # print(visited)
                return base+1
            if -1<item[0]+w[0]<n and \
                -1<item[1]+w[1]<m:  # 만약 이동한 곳에 길이 있다면
                if riddle[item[0]+w[0]][item[1]+w[1]] != 0 and \
                    not visited[item[0]+w[0]][item[1]+w[1]]:
                    riddle[item[0]+w[0]][item[1]+w[1]] = base+1
                    # print(w) 
                    # print(visited)
                    q.append([item[0]+w[0], item[1]+w[1]])
                    visited[item[0]+w[0]][item[1]+w[1]] = True
                    # print(item[1]+w[1], item[0]+w[0])

print(bfs(riddle))

알게 된 개념

얕은 복사 vs 깊은 복사

처음에 2차원 방문 배열을 아래와 같이 만들었고,

    visited = [[False]*m]*n
    visited[0][0] = True
    print(visited)

    >> [[True, False, False, False, False, False], [True, False, False, False, False, False], [True, False, False, False, False, False], [True, False, False, False, False, False]]

결과는 위와 같았다.
즉, [0][0]에만 True를 대입했다고 생각했지만, 전반적으로 모든 0번째 위치에 True가 대입 된거다!
1차원 리스트는 문제가 없다.

a = [0]*5
a[1] = 1
print a

a = [0 for i in xrange(5)]
a[1] = 1
print a

출력을 해보면 동일하게 의도한대로 출력된다.
이는 파이썬의 mutable과 immutable 속성 때문에 일어난다.

참고

[Python 변수] mutable과 immutable의 차이