[백준] 2206 벽부수고 이동하기 python

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

import sys
sys.stdin = open('2206_input.txt','r')

from collections import deque
n, m = map(int, input().split())
matrix = [input() for _ in range(n)]
visit = [[(-1, True)] * m for _ in range(n)]
visit[0][0] = (1, True)
q = deque([(0, 0)])
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(q):
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if 0 > dx or n <= dx or 0 > dy or m <= dy: continue
            if visit[x][y][1] == False:
                if visit[dx][dy][0] != -1: continue
                if matrix[dx][dy] == '0':
                    if visit[dx][dy][1]== True and (visit[x][y][0] > visit[dx][dy][0] > -1): continue
                    q.append((dx, dy))
                    visit[dx][dy] = (visit[x][y][0] + 1, visit[x][y][1])
            else:
                if visit[dx][dy][1] and visit[dx][dy][0] != -1: continue
                if matrix[dx][dy] == '0':
                    if visit[dx][dy][1] and visit[x][y][0] > visit[dx][dy][0] > -1: continue
                    q.append((dx, dy))
                    visit[dx][dy] = (visit[x][y][0] + 1, visit[x][y][1])
                elif matrix[dx][dy] == '1':
                    q.append((dx, dy))
                    visit[dx][dy] = (visit[x][y][0] + 1, False)

        if visit[n - 1][m - 1][0] != -1:
            break

bfs(q)
print(visit[n - 1][m - 1][0])

python으로는 시간초과가 걸리고 pypy로 성공했다.

구현하고 싶었던 것은 일반적인 BFS에 벽을 부쉈는지를 계속 체크하면서 나아가는 것이다.

이때 왔던길은 되돌아가면 안되고 벽을 부수지 않은 경우에는 벽을 부순길을 다시갈수 있다는 조건을 걸었다.

그랬을때 벽을 부순 상태라면 -1인 상태를 확인해야했고, 벽을 부수지 않은 상태이면 -1인곳(벽포함), 본인보다 작은데 벽을 부순곳을 확인해야했다.

구현하면 내가 쓴 코드처럼 if문으로 떡칠한 것이 나온다.

---

from collections import deque
n, m = map(int, input().split())
matrix = [list(map(int, list(input()))) for _ in range(n)]
visit = [[[0] * 2 for _ in range(m)] for _ in range(n)] # 벽을 부순경우, 부수지 않은 경우
visit[0][0][0] = 1
q = deque([(0, 0, 0)])
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(q):
    while q:
        x, y, z = q.popleft()
        if x == n - 1 and y == m -1:
            return visit[x][y][z]
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if 0 > dx or n <= dx or 0 > dy or m <= dy: continue
            if not matrix[dx][dy] and not visit[dx][dy][z]:
                visit[dx][dy][z] = visit[x][y][z] + 1
                q.append((dx, dy, z))
            elif not z and matrix[dx][dy] and not visit[dx][dy][1]:
                visit[dx][dy][1] = visit[x][y][z] + 1
                q.append((dx, dy, 1))
    return -1

print(bfs(q))

다른사람의 코드인데 간결해보여서 가져왔다.

이 코드는 일반적인 BFS에 벽을 부수지 않은 상태와 부순 상태를 두개로 나누어서 확인하는 코드이다.

아예 이렇게 두개로 나눠서 진행하는게 덮어씌우지않아도 되고 if문으로 떡칠하지 않아도 되어서 훨씬 낫다.

 

어...? pypy는 if문 떡칠한게 메모리 더 적게쓰고 속도가 빠르다