[Python/백준] 2206 벽 부수고 이동하

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

2206번: 벽 부수고 이동하기

<문제 해설>

BFS 너비우선 탐색 문제입니다. 이 문제는 고려해야할 것들이 좀 있습니다.

1. 벽을 부수고 이동하는 중인지 벽을 부수지 않고 이동하는 중인지 알수 있도록 기록해야 합니다.
2. 방문한 지점을 다시 방문하지 않기위해 방문한 지점을 기록해야 합니다.
3. 1,2과 연결되는데 벽을 부수지 않고 이동할때 벽을 부수고 이동하는 지점을 다시 방문할 수 있습니다. 이렇게 하지 않을시 나중에 벽을 뚫지 못해서 이동할수 있음에도 이동할수 없는 경우가 생깁니다. 따라서 벽을 부수고 이동하는 경우 방문했다는 기록을 다른방식으로 기록합니다.
4. N = 1, M = 1이여도 이동한거리가 1이됩니다. 따라서 거리를 재는 count 함수를 신경써줍니다.

이정도로 정리해 볼수 있는거 같습니다. 이제 방문한 지점을 표시한 2차원 배열과 벽이 표시되어있는 2차원배열을 만들고 현재 깊이에서 방문한 node들을 기록하고 그 node들을 너비우선 탐색으로 재귀시켜 이동시키면 됩니다.

<예시>

본 사진은 문제 예제 입력 1입니다. Wall배열에 벽을 1로 표시했습니다. Visit배열은 아래 코드를 다 돌리고난 후입니다. 벽을 부수지 않고 이동한곳은 1로 표기되어있고 벽을 부수고이동한 0,1이후부터는 2로 표시되어있습니다. 지나가지 않은 곳은 0으로 표시되어 있습니다.

다음 사진은 N = 2, M = 4일때를 나타냈습니다. 이번 예제에는 문제 해설에 적은 3번을 무시하면 풀리지 않을 수도 있습니다. x축으로 먼저 이동하는 방식을 쓴다면 벽을 뚫고 이동하는 방식이 1,1에 먼저 도착하게되고 종착지에 도착할 수 없습니다. 

<코드>

import sys

def bfs(node,count):
    nextnode =[]
    for yxz in node:
        for mv in move:
            y = yxz[0] + mv[0]
            x = yxz[1] + mv[1]
            if y == N-1 and x == M-1:
                print(count)
                return
            if 0 <= y < N and 0 <= x < M:
                if yxz[2] == 0:
                    if visit[y][x] != 1:
                      if wall[y][x] == '0':
                          visit[y][x] = 1
                          nextnode.append([y,x,0])
                      elif wall[y][x] == '1':
                          visit[y][x] = 1
                          nextnode.append([y,x,1])
                else:
                    if visit[y][x] == 0:
                        if wall[y][x] == '0':
                            visit[y][x] = 2
                            nextnode.append([y,x,1])
    if len(nextnode) == 0:
        print(-1)
        return
    else:
        bfs(nextnode,count+1)

N, M = list(map(int,sys.stdin.readline().rstrip().split()))

wall = []
visit = []
move = [[0,1],[0,-1],[1,0],[-1,0]]
for i in range(N):
    wall.append(list(input()))
    visit.append([0]*M)
visit[0][0]=1
node = [[0,0,0]]
if N == 1 and M == 1:
    print(1)
else:
    bfs(node,2)

<코드 설명>

import sys //sys 라이브러리를 사용하기위한 import

def bfs(node,count): //bfs호출 함수 인자로 node들이 저장되어 있는 배열과 깊이를 저장하는 count를 넘겨준다.
    nextnode =[] //노드들이 이동한 곳을 저장할 배열 다음 함수로 넘겨줄거다
    for yxz in node: //node에 있는 값들을 빼준다.
        for mv in move: //x좌표 1이동한번 -1이동 한번, y좌표 1이동 한번 -1이동 한번 해준다.
            y = yxz[0] + mv[0] //y값이 이동하는 과정을 y값에 저장한다.
            x = yxz[1] + mv[1] //x값이 이동하는 과정을 x값에 저장한다.
            if y == N-1 and x == M-1:  //종착지에 도착했을 경우 더이상 계산할 필요가없다.BFS기 때문에 처음 도착했을 때의 count가 가장 최잔 거리이다.
                print(count) //종착지 도착했으니 count 출력
                return //재귀함수도 종료
            if 0 <= y < N and 0 <= x < M: //지정된 배열 밖으로 벗어나지 않게 해주는 분기점
                if yxz[2] == 0: //노드의 3번째 배열에는 벽을 부수고 이동하는지 여부가 저장되고 0일경우 벽을 부수지 않고 이동하는 중이다.
                    if visit[y][x] != 1: //이동한 곳이 방문하지 않은 곳이라면 혹은 벽을 부수고 방문한 곳이라면
                      if wall[y][x] == '0': //그곳에 벽이 없다면
                          visit[y][x] = 1 //방문했다고 표시한다.
                          nextnode.append([y,x,0]) //이동한 노드를 다음 함수로 넘겨준다
                      elif wall[y][x] == '1': //벽이 있다면
                          visit[y][x] = 1 //방문했다고 표시한다
                          nextnode.append([y,x,1]) //이동한 노드를 다음 함수로 넘겨주지만 벽을 부순표식인 1을 넣어준다.
                else: //벽을 부수고 이동하고 있는 중이라면
                    if visit[y][x] == 0: //방문적이 무조건 없어야만 이동 가능하다.
                        if wall[y][x] == '0': //무조건 벽이 없어야만 이동 가능하다.
                            visit[y][x] = 2 //방문한 표시를 2로 해서 벽 안부수고 이동하는 애들이 이동할수 있게 한다.
                            nextnode.append([y,x,1]) //벽부수고 이동한다는 표식 1넣어서 다음 함수로 넘겨주기
    if len(nextnode) == 0: //다음 함수로 넘겨주는 지점이 없으면 더이상 갈 곳이 없다는 것이니
        print(-1) //도착지에 도착할 수 없다는 뜻이라 -1 출력
        return //함수도 종료
    else:
        bfs(nextnode,count+1) //재귀함수 넘겨주고 count 1증가하기

N, M = list(map(int,sys.stdin.readline().rstrip().split())) //N,M값 정수로 받아오기

wall = [] //wall을 기록할 배열
visit = [] //visit을 기록할 배열
move = [[0,1],[0,-1],[1,0],[-1,0]] //움직임을 간단하게 나타내기 위한 배열
for i in range(N): //N만큼 반복해서
    wall.append(list(input())) //배열 만들기
    visit.append([0]*M) //배열 만들기
visit[0][0]=1 //처음 방문한곳 1로 기록하기
node = [[0,0,0]] //처음 시작하는 node 배열에 넣어주기
if N == 1 and M == 1: //시작점이 도착점이면 1출력하기
    print(1)
else:
    bfs(node,2) //아닐경우 count에 2넣어주고 함수 호출하기