[파이썬][백준 2667][🤍실버 1] 단지 번호 붙이기 (DFS, BFS)

🧞‍♂️ 난이도

🤍 실버 1

🧞‍♂️ 문제

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

🧞‍♂️ 내 풀이

그냥 dfs 때리면 된다

DFS 로 모든 집을 방문하면서

섬의 개수 찾기 식으로 단지 개수를 세면 된다 (complexCount)

그리고 각각 단지를 방문하면서 그 단지에있는 집을 세기 위해 count 라는 전역 변수에 접근하면서 구하면 된다.

단, DFS 가 끝날때마다 이 count 변수는 0으로 다시 설정해줘야한다

🧞‍♂️ 파이썬 코드

import sys
input = sys.stdin.readline

N = int(input())
grid = [list(input())[:-1] for _ in range(N)]

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

def dfs(x, y):
    global count
    if x < 0 or x >= N or y < 0 or y >= N or grid[x][y] == '0':
        return
    grid[x][y] = '0'
    count += 1 # add to house count
    for i in range(4):
        dfs(x + dx[i], y + dy[i])

houses = []
complexCount = count = 0
for i in range(N):
    for j in range(N):
        if grid[i][j] == '1':
            dfs(i, j)
            # complex
            complexCount += 1
            # house numbers
            houses.append(count)
            count = 0

print(complexCount)
for i in sorted(houses):
    print(i)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기