백준 Nr 2667 단지번호붙이기 [Python] 풀이

1. 문제 설정 확인

백준 2667번 링크

2. 문제 풀이

기본적인 DFS 완전탐색 문제이다. N X N의 2차원 배열을 재귀적으로 탐색해나간다.

3. 해답 코드

import sys #stdin 사용하기 위해서 import

def dfs_recursive(x, y) :
    visited[x][y] = 1
    global nums
    if graph[x][y] == 1 :
        nums += 1
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if visited[nx][ny] == 0 and graph[nx][ny] == 1 :
                dfs_recursive(nx, ny)

N = int(input())
graph = []
nums = 0
visited = [[0]*N for _ in range(N)]
numlist= []
for i in range(N) :
    graph.append(list(map(int, input())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for a in range(N):
    for b in range(N) :
        if graph[a][b] == 1 and visited[a][b] == 0 :
            dfs_recursive(a, b)
            numlist.append(nums)
            nums = 0

print(len(numlist))
for n in sorted(numlist) :
    print(n)

딱히 설명이 필요하지 않을 코드다. 구성은 다른 코드와 다르지 않게

• 입력단
• 해답 함수 총 두가지로 나뉜다. 입력을 받고, 입력을 받은 결과를 해답 함수(여기선 dfs_recursive)에 전달한다. 해당 문제에선 NxN의 2차원 배열을 함수에 매개변수로 전달하고, 배열을 DFS로 완전탐색해준다.

Source

• Baekjoon, 2022.07.18
• Pycharm