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

문제 이해

백준 2606번과 유사한 문제이다.

배추가 모여있는 네트워크 하나 당 지렁이가 한 마리 필요하므로, 이 문제 또한 네트워크의 개수를 찾아야 하는 문제이다.

Flood Fill 알고리즘
이런 알고리즘을 Flood Fill이라고 한다. 주어진 시작점으로부터 연결된 영역을 찾는 알고리즘으로, 이름 그대로 그림판에서 페인트 툴으로 색을 붓는 것을 떠올리면 이해가 쉽다.
주로 DFS&BFS 문제에서 자주 나오는 알고리즘이다.

그래프의 각 칸을 돌다가 배추가 심겨져있는 칸을 방문하면 배추를 뽑고(재방문하지 않기 위해 그 자리를 0으로 만들고), BFS를 수행한다.

BFS 풀이

from collections import deque
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
test_case = int(input())

def bfs(array, a, b):
    queue = deque()
    # (a,b)로 시작점을 설정한다.
    queue.append((a,b))
    # 방문 표시
    array[a][b] = 0

    while queue:
        x, y = queue.popleft()
        # 4방향에 대해서 수행
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
            
            # 밭의 범위를 넘어가면 반복문을 수행하지 않음
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
                
            # 상하좌우로 이동한 곳에 배추가 있다면
            if array[nx][ny]:
            	# 방문 표시하고
                array[nx][ny] = 0
                # 새로 방문할 곳을 큐에 추가
                queue.append((nx, ny))
                
	# 이 리턴을 안 해줘서 4번 실패했다. (멍청)
    return

for _ in range(test_case):
    # 입력 받기
    n,m,k = map(int, input().split())
    array = [[0] * m for _ in range(n)]

    for _ in range(k):
        x,y = map(int, input().split())
        array[x][y] = 1

    answer = 0
    # 모든 칸을 돌면서
    for i in range(n):
        for j in range(m):
        	# 배추가 있다면
            if array[i][j]:
            	# bfs 수행
                bfs(array, i, j)
                answer += 1
    print(answer)

DFS 풀이

같은 문제를 DFS로도 풀어보았다.

import sys
sys.setrecursionlimit(10000)

def dfs(array, x, y):
    # 배추가 없거나 이미 방문했던 곳이라면 방문하지 않음
    if not array[x][y]:
        return

    # 시작점 방문 처리(배추 뽑기)
    array[x][y] = 0
    for dx, dy in direction:
        nx = x + dx
        ny = y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 배추가 없거나 이미 방문했던 곳이라면 방문하지 않음
        if not array[nx][ny]:
            continue
        # 상하좌우에 대해서 다시 dfs
        dfs(array, nx, ny)


for _ in range(test_case):
    answer = 0
    n,m,k = map(int, input().split())
    array = [[0] * m for _ in range(n)]

    for _ in range(k):
        x,y = map(int, input().split())
        array[x][y] = 1

    for i in range(n):
        for j in range(m):
            if array[i][j]:
                dfs(array, i, j)
                answer += 1
    print(answer)

주의할 점

import sys
sys.setrecursionlimit(10000)

DFS 풀이의 맨 윗줄에 이 코드가 꼭 있어야 Runtime Error 없이 성공 채점을 받을 수 있다. 파이썬에서 재귀를 이용해서 풀어야 하는 문제라면 위 두줄의 코드를 꼭 써줘야 한다. 파이썬의 재귀 깊이 제한은 1000이기 때문에, Runtime Error를 피하기 위해서 재귀의 깊이를 지정해줘야 한다.

실전 코딩테스트에서 꼭 알아둬야 할 꿀팁이다!

배운 점

• setrecursionlimit(10000) 기억하자.
• import sys를 허용하지 않는 코딩테스트가 있을 수도 있다.
  • BFS와 DFS 두 가지 알고리즘을 모두 능숙하게 쓸 수 있도록 연습하자.