99클럽 코테 스터디 8일차 TIL + 백준 2667 단지번호붙이기 (파이썬)

※ 2667 단지번호붙이기

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

문제 해결 TIP

해당 문제는 dfs로도, bfs로도 풀 수 있다.

 

전체 코드

dfs로 풀기

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

def dfs(x,y):
    if x<=-1 or x>=N or y<=-1 or y>=N:
        return False
    if graph[x][y] == 1:
        graph[x][y] = result+2
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

result = 0
for i in range(N):
    for j in range(N):
        if dfs(i,j) == True:
            result += 1
print(result)

house = []
for i in range(result):
    count = 0
    for row in graph:
        count += row.count(i+2)
    house.append(count)
house = sorted(house)
for i in house:
    print(i)
#graph = [[0, 2, 2, 0, 3, 0, 0], [0, 2, 2, 0, 3, 0, 3], [2, 2, 2, 0, 3, 0, 3], [0, 0, 0, 0, 3, 3, 3], [0, 4, 0, 0, 0, 0, 0], [0, 4, 4, 4, 4, 4, 0], [0, 4, 4, 4, 0, 0, 0]]

 

bfs로 풀기

from collections import deque

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

def bfs(x,y,visited):
    queue = deque()
    queue.append((x,y))
    count = 1
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))
                count += 1
    return count

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

complex_sizes = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and not visited[i][j]:
            complex_size = bfs(i,j,visited)
            complex_sizes.append(complex_size)
print(len(complex_sizes))
for size in sorted(complex_sizes):
    print(size)

---

• 비기너 문제 : 양과늑대 https://school.programmers.co.kr/learn/courses/30/lessons/92343
• 미들러 문제 : 단지번호붙이기 https://www.acmicpc.net/problem/2667
• 챌린저 문제 : 아 맞다 마늘 https://www.acmicpc.net/problem/32978