백준 2206 파이썬 풀이 (BFS, 벽 부수고 이동하기, 이차 배열 사용)

이 문제는 정말 나를 못살게 괴롭히는 놈이었다. 배열을 어떻게 해야할지 어떤 기준으로 visited를 하게 할지 굉장히 고민을 많이 하게 만들었다. 3차원 배열로 풀으라는데 내 방식대로 풀기 위해 상당히 고생을 했다.

 

우선 경우를 나누어본다. 벽을 뿌수고 이동하는 경우에는 다양하게 길이 갈리게 된다. 따라서 이미 누군가 지나간 길에 대해서 계속 갈지 말지를 정해야한다. 편의상 플레이어(경로를 가는 포인트)와 스킬(벽을 부쉈는지 아닌지)이라고 하겠다.

그렇다면 4가지 경우로 나눈다.

1. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적

2. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 마주쳤을때 => 더 이상 진행할 이유가 없다. 앞선 플레이어가 더 효율적

3. 스킬을 쓴 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 진행해야한다. 왜냐면 이미 스킬을 쓴 플레이어는 막다른 길에서 막혔을 수 있다.

4.  스킬을 쓴 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적

 

그럼 결과적으로 스킬을 쓴 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 진행하기만 하면 된다. 이외에는 더이상 진행시키지 않는다.

 

따라서 스킬을 이미 쓴 플레이어가 지나간 자리를 표시하고, 스킬을 쓰지 않은 플레이어가 지나간 자리를 표시하면 된다.

따라서 나는 Map에 한꺼번에 표시하기 위해 flag를 정의했다.

0 : 어떤경우든 갈 수 있음(묻지도 따지지도 않고 갈 수 있다.)

1 : 벽이기 때문에 못감 (단, 스킬을 가진경우 갈 수 있다.)

2 : 스킬을 쓰지 않은 유저가 지나간 흔적

3 : 스킬을 쓴 유저가 지나간 흔적 

 

갈수 있는 경우를 표로 나타내면 아래와 같다. 

	X 못감	O 갈수 있음
스킬 있음(2)	2	0 1 3
스킬 없음(3)	1 2 3	0

 

그럼 이를 토대로 코딩을 진행한다.

from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
M = []
for i in range(n):
    tmp = list(map(int, input().rstrip()))
    M.append(tmp)

def BFS():
    dx = [0,0,1,-1] #동 서 남 북
    dy = [1,-1,0,0]
    q = deque([[0,0,0]])
    if n == 1 and m == 1:
        if M[0][0] == 1:
            return -1
        else:
            return 1
    M[0][0] = 2
    time = -1
    while q:
        time += 1
        for _ in range(len(q)):
            x,y,z = q.popleft()
            if [x,y] == [n-1,m-1]:
                return time+1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0<=nx<n) and (0<=ny<m): #인덱스 허용범위
                    if z == 0: #벽뿌를 안함
                        if M[nx][ny] == 0:
                            M[nx][ny] = 2
                            q.append([nx,ny,z])
                        elif M[nx][ny] == 1:
                            q.append([nx,ny,1])
                        elif M[nx][ny] == 3:
                            q.append([nx,ny,z])
                            M[nx][ny]=2
                    else: #벽뿌를 함
                        if M[nx][ny] == 0:
                            M[nx][ny] = 3
                            q.append([nx,ny,z])
    return -1
print(BFS())

의외로 이러한 방법으로 풀렸다....ㅋㅋㅋㅋㅋㅋ

그래서 다른 코드를 보니까 3차원으로 visited를 만들어서 푼 코드를 확인 할 수 있었다. 다음에 기회가 되면 3차원 visited로 풀어봐야겠다.