0218. [BOJ#2178] 미로 탐색

1 초

192 MB

191754

87058

55359

43.902%

문제

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

출력

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

---

 

제출 코드 (state3)

def bfs(si, sj):
    global N, M
    Queue = []
    Queue.append((si, sj))
    visited[0][0] = 1
    
    while Queue:
        ci, cj = Queue.pop(0)
        for k in range(4):
            ki = ci + di[k]
            kj = cj + dj[k]
            if 0 <= ki < N and 0 <= kj < M:
                if arr[ki][kj] == 1 and visited[ki][kj] == 0:
                    visited[ki][kj] = visited[ci][cj] + 1
                    Queue.append((ki, kj))
                    if ki == (N-1) and kj == (M-1):
                        print(visited[ki][kj])
                        break


di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
start_i, start_j = (0, 0) # 시작점 설정
bfs(start_i, start_j)

 

첫 블록도 포함한다고 해서 visited = 1로 시작하여 pop된 좌표중 값이 1이고, 처음 도착한 곳을 지날 때,

visited에 +1로 카운트를 해주었다. 한번 지났던 곳은 다시 지나지 않고 Queue 안에서 값을 꺼내오기 때문에 visited값의 변동이 없는 점을 이용해 카운트가 잘된것같다.

제출 코드 (state2)

def bfs(si, sj):
    global N, M
    Queue = []
    Queue.append((si, sj))
    visited[0][0] = 1
    
    cnt = 1
    while Queue:
        ci, cj = Queue.pop(0)
        for k in range(4):
            ki = ci + di[k]
            kj = cj + dj[k]
            if 0 <= ki < N and 0 <= kj < M:
                if arr[ki][kj] == 1 and visited[ki][kj] == 0:
                    visited[ki][kj] = 1
                    cnt += 1 
                    Queue.append((ki, kj))
                    if ki == (N-1) and kj == (M-1):
                        print(cnt)
                        break
                    elif len(Queue) >= 2:
                        cnt -= 1


di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
start_i, start_j = (0, 0) # 시작점 설정
bfs(start_i, start_j)

시행착오였던 코드인데 cnt를 초기화해서 새로운 곳을 지날때마다 cnt += 1을 해주는 방식으로 진행했다.

하지만 막힌 길에 들어갔을 때도 카운트 해버리는 것에 대한 조건을 구현해내지 못하여 state3 방식으로 바꿨다.