직접 풀어보자! BFS와 DFS 5문제

안녕, 나 코딩냥이다냥! 오늘 다섯 문제는 뼈대가 전부 같다냥. 1번을 제대로 짜두면 나머지는 거기에 한두 줄씩 더하는 것뿐이라냥. 그러니 1번에 시간을 넉넉히 쓰자냥.

탐색 문제를 풀 때 순서

무엇이 점이고 무엇이 연결인지 정한다 — 칸이냥, 정점이냥?
어디서 시작하는지 정한다 — 한 곳이냥, 여러 곳이냥?
무엇을 기록하는지 정한다 — 방문 여부냥, 거리냥?

3번이 문제마다 달라지는 부분이라냥. 나머지 둘은 거의 안 바뀐다냥.

미션 1섬의 개수20분

상하좌우로 이어진 땅 덩어리가 몇 개인지 센다냥.

문제 풀러 가기

뼈대안 가본 땅에서 탐색을 시작한 횟수라냥

격자를 전부 훑으면서, 아직 안 가본 땅을 만나면 거기서 탐색을 시작한다냥. 그 한 번의 탐색이 섬 하나를 통째로 방문 표시한다냥.

시작한 횟수가 곧 섬의 개수라냥.

for r in range(n):
    for c in range(m):
        if grid[r][c] == '#' and not seen[r][c]:
            cnt += 1
            # 여기서 BFS 나 DFS 로 이 섬 전체를 표시한다냥

대각선은 이어진 것으로 보지 않는다냥. 방향표를 상하좌우 네 개만 쓰자냥.

8장에서 여덟 방향을 썼다고 그대로 가져오면 틀린다냥.

방문 표시는 큐에 넣을 때 하자냥. 꺼낼 때 하면 같은 칸이 큐에 여러 번 쌓인다냥.

미션 2가장 큰 영역15분

가장 큰 땅 덩어리가 몇 칸인지 출력한다냥.

문제 풀러 가기

1번과 뼈대가 똑같다냥. 세는 대상만 바뀐다냥.

탐색을 시작한 횟수가 아니라, 한 번의 탐색에서 꺼낸 칸 수를 세면 된다냥. 그중 제일 큰 값이 답이라냥.

재귀 DFS 로 풀 거면 이 줄이 꼭 필요하다냥.

import sys
sys.setrecursionlimit(10 ** 6)

숨겨진 테스트에 100 x 100이 전부 땅인 격자가 있다냥. 빈틈이 없어서 재귀가 10000단계까지 파고든다냥. 이 줄이 없으면 정답 코드도 RecursionError 로 터진다냥.

BFS 로 풀면 이 걱정이 아예 없다냥.

확인땅이 하나도 없으면 0 이라냥

공개된 예시에 1 1 짜리 물 한 칸이 들어 있다냥.

최댓값을 구할 때 시작값을 잘못 잡으면 여기서 틀린다냥.

미션 3미로 최단 거리25분

왼쪽 위에서 오른쪽 아래까지 지나는 칸 수를 최소로 한다냥.

문제 풀러 가기

반드시 BFS 로 풀어야 한다냥.

DFS 로 먼저 도착한 경로를 답으로 쓰면 틀린다냥. DFS 는 한 방향으로 끝까지 파고들어서 빙 돌아가는 길로 먼저 닿을 수 있다냥.

숨겨진 테스트에 그걸 잡는 큰 미로가 들어 있다냥.

뼈대방문 표시 대신 거리를 적는다냥

dist = [[-1] * m for _ in range(n)]
dist[0][0] = 1
q = deque([(0, 0)])

while q:
    r, c = q.popleft()
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if not (0 <= nr < n and 0 <= nc < m):
            continue                       # 격자 밖이라냥
        if grid[nr][nc] == '#':
            continue                       # 벽이라냥
        if dist[nr][nc] != -1:
            continue                       # 이미 갔다냥
        dist[nr][nc] = dist[r][c] + 1
        q.append((nr, nc))

-1 이 곧 "아직 안 감"이라 seen 을 따로 둘 필요가 없다냥.

답은 이동 횟수가 아니라 지나는 칸의 개수라냥. 시작과 도착을 모두 포함한다냥. 그래서 시작 칸을 1 로 놓고 시작하는 거라냥.

1 1 짜리 격자의 답이 1 인지 확인해보면 감이 잡힌다냥.

시작이나 도착이 벽일 수도 있다냥. 탐색을 시작하기 전에 먼저 확인하자냥. 도착이 벽이면 당연히 -1 이라냥.

미션 4그래프 탐색 순서20분

격자가 아닌 그래프에서 BFS 방문 순서를 출력한다냥.

문제 풀러 가기

알고리즘은 하나도 안 바뀐다냥. 이웃을 주는 곳이 방향표에서 인접 리스트로 바뀔 뿐이라냥.

for nxt in adj[cur]:      # DIRS 자리에 adj[cur] 가 온다냥
    if not seen[nxt]:
        seen[nxt] = True
        q.append(nxt)

인접 리스트를 정렬해야 한다냥. 번호가 작은 정점부터 방문하라고 했기 때문이라냥.

정렬하지 않으면 입력에 적힌 순서대로 방문해서 답이 달라진다냥. 숨겨진 테스트가 이걸 잡는다냥.

for a in adj:
    a.sort()

확인갈 수 없는 정점은 출력하지 않는다냥

시작 정점에서 이어지지 않은 정점은 아예 빼고 출력한다냥.

공개된 예시에 그런 경우가 들어 있다냥. 정점 번호를 1번부터 n번까지 전부 출력하면 틀린다냥.

미션 5여러 곳에서 동시에 번지기25분

모든 빈 칸이 채워지는 최소 단계를 구한다냥.

문제 풀러 가기

시작점을 하나씩 탐색할 필요가 없다냥.

시작점을 전부 큐에 넣고 시작하면 물결이 동시에 퍼진다냥. 그러면 한 번의 BFS 로 끝난다냥. 이게 오늘의 마지막 요령이라냥.

for r in range(n):
    for c in range(m):
        if grid[r][c] == '*':
            dist[r][c] = 0
            q.append((r, c))

확인세 가지 경우를 다 처리하자냥

빈 칸이 처음부터 없으면 → 0
끝까지 채우지 못한 빈 칸이 있으면 → -1
그 외에는 → 가장 마지막에 채워진 칸의 단계 수

빈 칸 개수를 미리 세어두고, 채울 때마다 하나씩 줄이면 편하다냥. 끝나고도 남아 있으면 -1 이라냥.

답은 단계 수라냥. 시작점은 0단계라서 시작점만 있고 빈 칸이 없으면 답이 0 이라냥.

공개된 예시에 1 1 짜리 시작점 하나가 들어 있으니 그걸로 확인하자냥.

다섯 개 다 풀었냥? 리스트에서 시작해서 탐색까지 왔다냥. 여기서 배운 BFS 뼈대는 앞으로 만날 대부분의 탐색 문제에서 거의 그대로 쓰인다냥.

다음은 완전탐색이라냥. 똑똑한 방법이 안 떠오를 때 쓰는, 가장 든든한 무기라냥. 정말 수고했다냥~

직접 풀어보자! BFS와 DFS 5문제

탐색 문제를 풀 때 순서

무엇이 점이고 무엇이 연결인지 정한다 — 칸이냥, 정점이냥?
어디서 시작하는지 정한다 — 한 곳이냥, 여러 곳이냥?
무엇을 기록하는지 정한다 — 방문 여부냥, 거리냥?

3번이 문제마다 달라지는 부분이라냥. 나머지 둘은 거의 안 바뀐다냥.

미션 1섬의 개수20분

상하좌우로 이어진 땅 덩어리가 몇 개인지 센다냥.

문제 풀러 가기

뼈대안 가본 땅에서 탐색을 시작한 횟수라냥

격자를 전부 훑으면서, 아직 안 가본 땅을 만나면 거기서 탐색을 시작한다냥. 그 한 번의 탐색이 섬 하나를 통째로 방문 표시한다냥.

시작한 횟수가 곧 섬의 개수라냥.

for r in range(n):
    for c in range(m):
        if grid[r][c] == '#' and not seen[r][c]:
            cnt += 1
            # 여기서 BFS 나 DFS 로 이 섬 전체를 표시한다냥

대각선은 이어진 것으로 보지 않는다냥. 방향표를 상하좌우 네 개만 쓰자냥.

8장에서 여덟 방향을 썼다고 그대로 가져오면 틀린다냥.

방문 표시는 큐에 넣을 때 하자냥. 꺼낼 때 하면 같은 칸이 큐에 여러 번 쌓인다냥.

미션 2가장 큰 영역15분

가장 큰 땅 덩어리가 몇 칸인지 출력한다냥.

문제 풀러 가기

1번과 뼈대가 똑같다냥. 세는 대상만 바뀐다냥.

탐색을 시작한 횟수가 아니라, 한 번의 탐색에서 꺼낸 칸 수를 세면 된다냥. 그중 제일 큰 값이 답이라냥.

재귀 DFS 로 풀 거면 이 줄이 꼭 필요하다냥.

import sys
sys.setrecursionlimit(10 ** 6)

BFS 로 풀면 이 걱정이 아예 없다냥.

확인땅이 하나도 없으면 0 이라냥

공개된 예시에 1 1 짜리 물 한 칸이 들어 있다냥.

최댓값을 구할 때 시작값을 잘못 잡으면 여기서 틀린다냥.

미션 3미로 최단 거리25분

왼쪽 위에서 오른쪽 아래까지 지나는 칸 수를 최소로 한다냥.

문제 풀러 가기

반드시 BFS 로 풀어야 한다냥.

DFS 로 먼저 도착한 경로를 답으로 쓰면 틀린다냥. DFS 는 한 방향으로 끝까지 파고들어서 빙 돌아가는 길로 먼저 닿을 수 있다냥.

숨겨진 테스트에 그걸 잡는 큰 미로가 들어 있다냥.

뼈대방문 표시 대신 거리를 적는다냥

dist = [[-1] * m for _ in range(n)]
dist[0][0] = 1
q = deque([(0, 0)])

while q:
    r, c = q.popleft()
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if not (0 <= nr < n and 0 <= nc < m):
            continue                       # 격자 밖이라냥
        if grid[nr][nc] == '#':
            continue                       # 벽이라냥
        if dist[nr][nc] != -1:
            continue                       # 이미 갔다냥
        dist[nr][nc] = dist[r][c] + 1
        q.append((nr, nc))

-1 이 곧 "아직 안 감"이라 seen 을 따로 둘 필요가 없다냥.

답은 이동 횟수가 아니라 지나는 칸의 개수라냥. 시작과 도착을 모두 포함한다냥. 그래서 시작 칸을 1 로 놓고 시작하는 거라냥.

1 1 짜리 격자의 답이 1 인지 확인해보면 감이 잡힌다냥.

시작이나 도착이 벽일 수도 있다냥. 탐색을 시작하기 전에 먼저 확인하자냥. 도착이 벽이면 당연히 -1 이라냥.

미션 4그래프 탐색 순서20분

격자가 아닌 그래프에서 BFS 방문 순서를 출력한다냥.

문제 풀러 가기

알고리즘은 하나도 안 바뀐다냥. 이웃을 주는 곳이 방향표에서 인접 리스트로 바뀔 뿐이라냥.

for nxt in adj[cur]:      # DIRS 자리에 adj[cur] 가 온다냥
    if not seen[nxt]:
        seen[nxt] = True
        q.append(nxt)

인접 리스트를 정렬해야 한다냥. 번호가 작은 정점부터 방문하라고 했기 때문이라냥.

정렬하지 않으면 입력에 적힌 순서대로 방문해서 답이 달라진다냥. 숨겨진 테스트가 이걸 잡는다냥.

for a in adj:
    a.sort()

확인갈 수 없는 정점은 출력하지 않는다냥

시작 정점에서 이어지지 않은 정점은 아예 빼고 출력한다냥.

공개된 예시에 그런 경우가 들어 있다냥. 정점 번호를 1번부터 n번까지 전부 출력하면 틀린다냥.

미션 5여러 곳에서 동시에 번지기25분

모든 빈 칸이 채워지는 최소 단계를 구한다냥.

문제 풀러 가기

시작점을 하나씩 탐색할 필요가 없다냥.

시작점을 전부 큐에 넣고 시작하면 물결이 동시에 퍼진다냥. 그러면 한 번의 BFS 로 끝난다냥. 이게 오늘의 마지막 요령이라냥.

for r in range(n):
    for c in range(m):
        if grid[r][c] == '*':
            dist[r][c] = 0
            q.append((r, c))

확인세 가지 경우를 다 처리하자냥

빈 칸이 처음부터 없으면 → 0
끝까지 채우지 못한 빈 칸이 있으면 → -1
그 외에는 → 가장 마지막에 채워진 칸의 단계 수

빈 칸 개수를 미리 세어두고, 채울 때마다 하나씩 줄이면 편하다냥. 끝나고도 남아 있으면 -1 이라냥.

답은 단계 수라냥. 시작점은 0단계라서 시작점만 있고 빈 칸이 없으면 답이 0 이라냥.

공개된 예시에 1 1 짜리 시작점 하나가 들어 있으니 그걸로 확인하자냥.

다섯 개 다 풀었냥? 리스트에서 시작해서 탐색까지 왔다냥. 여기서 배운 BFS 뼈대는 앞으로 만날 대부분의 탐색 문제에서 거의 그대로 쓰인다냥.

다음은 완전탐색이라냥. 똑똑한 방법이 안 떠오를 때 쓰는, 가장 든든한 무기라냥. 정말 수고했다냥~