[Python] 백준 2206 & 백준 1697

# 백준 2206

from collections import deque
n, m = map(int, input().split(' '))

graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
d_row = [0, -1, 0, +1]
d_col = [+1, 0, -1, 0]
def bfs():
    queue = deque()
    queue.append([0,0,0])
    visited[0][0][0] = 1
 # w = 0이면 벽을 뚫지 않고 간 경우, w = 1이면 벽을 뚫고 간 경우
    while queue:
        x,y,w = queue.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][w]
        for i in range(4):
            nx, ny = x+d_row[i], y+d_col[i]
            if nx < 0 or ny< 0 or nx> n-1 or ny > m-1:
                continue
            # 다음 위치가 0이고 , 아직 방문하지 않았다면(방문했으면 1)
            if graph[nx][ny] == 0 and visited[nx][ny][w] == 0:
                visited[nx][ny][w] = visited[x][y][w] + 1
                queue.append([nx,ny,w])
            # 다음 위치가 벽이고, 벽을 아직 부수지 않았다면(w == 0)
            elif graph[nx][ny] == 1 and w == 0:
                visited[nx][ny][w+1] = visited[x][y][w] + 1 # visited +1은 방문처리한거, w+1 은 벽을 부셨다는 의미
                queue.append([nx,ny,w+1])
    return -1

print(bfs())

 

 

 

# 백준 1697
import sys
from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            return visited[x]
        for nx in (x * 2, x + 1, x - 1):
            if 0 <= nx <= 100001 and not visited[nx]:
                visited[nx] = visited[x] + 1
                q.append(nx)

n, k = map(int, sys.stdin.readline().split())
visited = [0 for i in range(100001)]
print(bfs())

📝 Points

3차원 vistied 그래프 사용하자