[김태원 알고리즘] 단지 번호 붙이기 (FloodFill - DFS & BFS)

사용 언어: Python3

문제

풀이

내 풀이 - DFS 사용

import sys
sys.setrecursionlimit(10**6)

dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y):
    global cnt
    visited[x][y] = 1 # ✅ visited 체크
    for w in range(4):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy] == 1:
            continue
        cnt += 1 # ✅ cnt 누적
        DFS(xx, yy)

N = int(input())
board = [list(map(int, input())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

res = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j] == 1: # ✅ 조건 체크
            continue
        cnt = 1 # ✅ flood fill은 1부터
        DFS(i, j)
        res.append(cnt) # res에 append

print(len(res))
for x in sorted(res): # ✅ 오름차순 정렬
    print(x)

• 정답!

다른 풀이 - BFS 사용

from collections import deque

dx, dy = [0,-1,0,1], [1,0,-1,0]
N = int(input())
board = [list(map(int, input())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

res = []
q = deque()
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j] == 1: # ✅ 조건 체크
            continue
        visited[i][j] = 1
        q.append((i, j))
        cnt = 1 # ✅ flood fill은 1부터
        while q:
            cur = q.popleft()
            for w in range(4):
                xx, yy = cur[0]+dx[w], cur[1]+dy[w]
                if xx<0 or xx>=N or yy<0 or yy>=N:
                    continue
                if board[xx][yy] == 0 or visited[xx][yy] == 1:
                    continue
                visited[xx][yy] = 1
                q.append((xx, yy))
                cnt += 1 # ✅ cnt 누적
        res.append(cnt) # res에 append

print(len(res))
for x in sorted(res): # ✅ 오름차순 정렬
    print(x)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기