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

문제

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

2206번: 벽 부수고 이동하기

 

---

풀이

from collections import deque

def bfs():
    q = deque()
    q.append([0,0,0])

    while q:
        cur_r, cur_c, breakable = q.popleft()

        if cur_r == row_len - 1 and cur_c == col_len - 1:
            return visited[cur_r][cur_c][breakable]

        for dr, dc in directions:
            next_r = cur_r + dr
            next_c = cur_c + dc

            if next_r <= -1 or next_r >= row_len or next_c <= -1 or next_c >= col_len:
                continue

            # 다음 이동할 곳이 벽이고 벽 파괴 기회를 사용하지 않은 경우 -> 벽 부수기
            if grid[next_r][next_c] == 1 and breakable == 0:
                visited[next_r][next_c][1] = visited[cur_r][cur_c][0] + 1
                q.append([next_r, next_c, 1])

            # 다음 이동할 곳이 벽이 아니고 한번도 방문하지 않음
            elif grid[next_r][next_c] == 0 and visited[next_r][next_c][breakable] == 0:
                visited[next_r][next_c][breakable] = visited[cur_r][cur_c][breakable] + 1
                q.append([next_r, next_c, breakable])

    return -1


row_len, col_len = map(int, input().split())
grid = [list(map(int, input())) for _ in range(row_len)]

visited = [[[0,0] for _ in range(col_len)] for _ in range(row_len)]     # 이건 됨
visited[0][0][0] = 1

directions = [(1,0), (-1,0), (0,1), (0,-1)]

print(bfs())

---

설명

이차원배열 형태로 최단경로를 구하라고 해서 bfs, dfs 문제 라는것을 알았다!

 

visited 배열 인덱스 처리하는 부분이 헷갈렸다. 벽을 1번만 부술 수 있기 때문에 벽을 부쉈는지의 여부에 따라서 경로가 달라진다. visited[next_r][next_c][breakable] 일 때 breakable 이 0이면 안 부쉈고, 1이면 부순 경로임을 의미한다.

=> bfs 탐색을 통해 "벽을 뚫은 경우"와 "그렇지 않은 경우" 두 가지 모두를 기록하는 것이다.