99클럽 코테 스터디 18일차 TIL + DFS/BFS

[오늘의 학습 키워드 및 문제]
- 백준의 "단지번호붙이기" 문제를 풀었다.
- 오늘 주제는 DFS/BFS로 까다로운 문제는 아니었다.

[나의 코드]

# BFS 풀이

from collections import deque

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    graph[x][y] = 0
    count = 1
    
    while q:
        x, y, = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = 0
                    count += 1
                    q.append((nx, ny))
    
    return count
                    
result = []                   
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            result.append(bfs(i, j))

result.sort()
print(len(result))
for num in result:
    print(num)

개인적으로 큐를 쓰는 BFS가 더 편해서 우선적으로 이 풀이로 풀었다.

visited 배열을 따로 만들어도 되지만, 그냥 1을 0으로 바꿔주는 코드로 구현했다.
그리고 맨 처음 들어가는 것도 계산을 해줘야 하기 때문에 그래프는 0으로 개수는 1부터 세준다.

큰 틀은 다음과 같다.
① 그래프에서 값이 1인 곳의 x와 y의 좌표를 큐에 넣는다.
② 큐가 있는 동안, 맨 앞의 좌표에 대한 네 방향을 확인한다.
③ 만약 인접 좌표가 그래프 크기를 벗어나지 않고, 값이 1이라면 count를 하나 올리고, 값을 0으로 바꾼다.
④ 그리고 해당 좌표를 큐에 넣어 준다.

# DFS 풀이

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

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

def dfs(x, y):
    global count
    
    visited[x][y] = True
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < n and 0 <= ny < n:
            if not visited[nx][ny]:
                if graph[nx][ny] == 1:
                    count += 1
                    dfs(nx, ny)
    return count

result = []
for i in range(n):
    for j in range(n):
        count = 1
        if not visited[i][j] and graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            
result.sort()
print(len(result))
for num in result:
    print(num)

내가 공부해본 바로는 이거는 BFS 보다는 DFS가 더 어울리는 문제이다.
그래서 DFS도 공부해 볼 겸, 추가로 더 풀어 보았다.

참고로 DFS가 속도가 더 빠르게 나왔다. DFS는 재귀로 푸는 것이 핵심이다.

[오늘의 회고]
- 오늘 문제는 어렵지 않았다. 10분 걸렸다.
- 탐색 문제는 대부분 저 코드를 바탕으로 짤 수 있기 때문에 기초가 중요한 것 같다.
- 다음에는 조금 더 어려운 문제를 찾아서 풀어봐야 겠다. 끝!