[백준(python)] 2606 단지번호붙이기

📌 난이도, 유형

난이도 : 실버1
유형 : DFS, BFS, 그래프
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

BFS(Breadth-First Search)

# BFS 풀이
from collections import deque

# 이동방향(상, 하, 좌, 우) 설정
dx = [0,0,-1,1] # 좌, 우
dy = [1,-1,0,0] # 상, 하

def bfs(graph, x, y):
	# 단지 탐색을 하고 난 후에 다시 탐색을 해야하니까 함수 안에 queue 선언해줌
    queue = deque()
    queue.append((x,y))
    # 들린 곳은 0으로 바꿔줌
    graph[x][y] = 0 
    # count = 단지에 속하는 집의 개수, 1로 시작하는 이유는 시작한 곳은 이미 방문한거니깐 0이 아니라 1로 시작
    count = 1 

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 지도를 벗어나는 경우에는 continue
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            # x, y가 아니라 nx, ny인 이유는 움직인 좌표(상하좌우)에서 집이 있는지 확인을 해야돼서
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                count += 1
	# 탐색이 끝나면 단지에 속하는 집의 수를 return 해줌
    return count

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

cnt = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            cnt.append(bfs(graph, i, j))

#문제에서 오름차순으로 정렬하라고 했음
cnt.sort()
print(len(cnt))
for i in cnt:
    print(i)

DFS(Depth-First Search)

# DFS 풀이
N = int(input())
graph = []
q = []
num = 0
for i in range(N):
    graph.append(list(map(int,input())))
# bfs할때 dx, dy랑 다른데 상관없음 1,-1끼리 겹치지만 않으면 됨
# ex) dx = [1, -1, 0, 0] , dy = [-1, 1, 0 ,0] (X)
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def dfs(x,y):
    global result
    if x <= -1 or y <= -1 or x >= N or y >= N:
        return False
    if graph[x][y] == 1
        graph[x][y] = 0
        result += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)
        return True
    return False

count = 0
result = 0

for i in range(N):
    for j in range(N):
        if dfs(i,j) == True:
            q.append(result)
            num += 1
            result = 0
print(num)
q.sort()
for i in q:
    print(i)

---

📝 해설

주석참고