문제

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline


def bfs():
    global res
    while dq:
        x, y, cnt, dr = dq.popleft()
        if x == n - 1 and y == m - 1:
            res = min(res, cnt)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] == 0 and visited[nx][ny][dr] == 0:
                    visited[nx][ny][dr] = 1
                    dq.append((nx, ny, cnt + 1, dr))
                elif arr[nx][ny] == 1 and dr == 0:
                    visited[nx][ny][1] = 1
                    dq.append((nx, ny, cnt + 1, 1))


n, m = map(int, input().split())
dq = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
arr = [[0 for i in range(m)] for i in range(n)]
visited = [[[0, 0] for i in range(m)] for i in range(n)]
dq.append((0, 0, 0, 0))
res = 10000000
for i in range(n):
    a = input()
    for j in range(m):
        arr[i][j] = int(a[j])
bfs()
if res == 10000000:
    print(-1)
else:
    print(res + 1)

설명

간단한 bfs 문제이다.

' 벽을 뚫고 갈 수 있다.'

이게 포인트 인데
처음에는 드릴을 뚫었나 안뚫었나 이것만 생각해서
visited 에는 count값, 오는데 걸린 횟수를 넣고
0 , 1 로 뚫고왔는지 안뚫고 왔는지를 체크했다.
이렇게 하니 11%에서 막혔다.
그래서 visited를 드릴을 뚫고 갔는지 안뚫고갔는지 두가지 경우로
3차원배열로 만들었다.
그리고 도착했을때 res값에 가장 작은 횟수로 도착한것을 저장
그리고 0부터 시작해서 res값 + 1을 해서 출력

후기

오랜만에 bfs문제를 풀었는데 꾸준히 한번씩 풀어줘야겠다...