DFS에 익숙해져보자 (문제 리스트)

DFS 문제 추천 블로그
위 블로그를 보고 DFS 문제를 좀 풀어봐야겠다.

그래프 탐색 문제의 경우

1. DFS or BFS 둘 다 무관한 경우
2. DFS를 사용하는것이 압도적으로 편한 경우
3. BFS를 사용하는것이 압도적으로 편한 경우

정도가 있겠다.

DFS, BFS를 선택할 때 어떤 기준으로?

본인이 더 익숙한 방식으로 풀어도 되는 경우가 많지만, 특정 알고리즘을 쓰는 것이 유리한 경우가 있다.

DFS
재귀, 백트래킹을 이용한 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제 (순열, 조합 등)

BFS
depth(깊이)를 이용한 문제 (최단경로 등)
가중치가 같은 그래프에서 최단거리를 찾을 때

골드3. 백준 2206 벽 부수고 이동하기

풀이 (해설참고)

현재까지 벽을 뚫은 여부만 단순히 갖고 접근하면 안된다. (이렇게 풀면 해당 좌표까지 벽을 뚫고 접근했을 때와 벽을 뚫지 않았을 때를 구분할 수 없다)

최단거리를 구하는 문제이기 때문에 BFS로 접근해서 풀면 된다. 다만 벽을 뚫었을 때의 거리와 벽을 뚫지 않았을 때의 거리를 계산해야 하므로 거리를 계산하는 배열을 3차원으로 갖고 있어야 한다.

• visit[0][row][col] : 벽을 뚫지 않고 해당 좌표까지 접근한 거리
• visit[1][row][col] : 벽을 뚫고 해당 좌표까지 접근한 거리

코드

from sys import stdin
from collections import deque

input = stdin.readline

# N : row, M : col
N, M = map(int, input().split(" "))

graph = [list(map(int, input().rstrip())) for _ in range(N)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

visit = [[[0 for _ in range(2)] for _ in range(M)] for _ in range(N)]


def bfs(sr, sc):
    # 벽 안 부순 상태 : 0
    q = deque([(sr, sc, 0)])
    visit[sr][sc][0] = 1
    while q:
        r, c, wall = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if visit[nr][nc][wall] == 0:
                    # 벽이 아니라면 이동
                    if graph[nr][nc] == 0:
                        q.append((nr, nc, wall))
                        visit[nr][nc][wall] = visit[r][c][wall] + 1
                # 벽 아직 안 부쉈고, 벽인 경우
                if wall == 0 and graph[nr][nc] == 1:
                    # 벽 부순 상태 : 1
                    q.append((nr, nc, 1))
                    # 이전경로 + 1 저장
                    visit[nr][nc][1] = visit[r][c][wall] + 1


bfs(0, 0)
max_dist = int(1e9)
if visit[N - 1][M - 1][1] != 0:
    max_dist = min(max_dist, visit[N - 1][M - 1][1])
if visit[N - 1][M - 1][0] != 0:
    max_dist = min(max_dist, visit[N - 1][M - 1][0])

if max_dist == int(1e9):
    print(-1)
else:
    print(max_dist)

크악 오늘 뭘 했다고 하루가 다 끝났냐!! 내일 하루종일 코테만 풀어주지