문제 설명

상, 하, 좌, 우로 인접한 구역의 개수를 카운트해서 출력하는 문제

풀이

모든 좌표를 돌면서
1이면서 visited==False인 좌표에 대해 DFS 수행
count += 1

DFS 구현 방법

현재 좌표에 대해 visited=True
네 방향을 모두 검사하여 재귀적으로 DFS 수행

코드

import sys


def init():
    w, h, k = map(int, ipt().split())
    board = [[0 for x in range(w)] for y in range(h)]
    visited = [[False for x in range(w)] for y in range(h)]
    for _ in range(k):
        x, y = map(int, ipt().split())
        board[y][x] = 1
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    return w, h, 0, visited, board, dx, dy


def out(pos):
    y, x = pos
    if 0 <= y < h and 0 <= x < w:
        return False
    return True


def dfs(start):
    y, x = start
    visited[y][x] = True
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if not out((ny, nx)):
            if board[ny][nx] == 1 and not visited[ny][nx]:
                dfs((ny, nx))


ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
    w, h, count, visited, board, dx, dy = init()
    for y in range(h):
        for x in range(w):
            if board[y][x] == 1 and not visited[y][x]:
                count += 1
                dfs((y, x))
    print(count)

문제 링크

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