[백준] 단지 번호 붙이기

[백준] 단지 번호 붙이기

문제

링크 : 백준

---

풀이

지도가 주어질 때, 단지 수와 단지 내의 아파트 수를 구하는 문제이다.
이 문제는 bfs, dfs 모두를 이용해서 풀어봤다.
여기서 중요한 점은 단지 수, 아파트 수를 세는 것인데
단지 수를 세기 위해서는 탐색을 들어갈 때 카운트를 하고
아파트 수를 세기 위해서는 탐색에서 카운트한 값을 가져온다.

# BFS
n = int(input())
graph = [list(map(int,input())) for _ in range(n)]
visit = [[0] * n for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
from collections import deque

def bfs(x, y, graph, start):
    deq = deque()
    deq.append([x, y])
    graph[x][y] = 0
    l = len(graph[x])
    while deq:
        x,y = deq.popleft()
        for i in range(4):
            mx = x + dx[i]
            my = y + dy[i]
            if mx >= 0 and my >= 0 and mx < l and my < l:
                if graph[mx][my] == 1 and visit[mx][my] == 0:
                    deq.append([mx, my])
                    visit[mx][my] = 1
                    start += 1
    return start

def solution(graph, n):
    answer = [0]
    count = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1 and visit[i][j] == 0:
                count.append(bfs(i, j, graph, 1))
                answer[0] += 1

    count = sorted(count)
    answer.extend(count)
    for i in range(len(answer)):
        print(answer[i])

solution(graph, n)

# DFS
n = int(input())
graph = [list(map(int,input())) for _ in range(n)]
visit = [[0] * n for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
from collections import deque
def dfs(x, y, ans):
    for i in range(4):
        mx = x + dx[i]
        my = y + dy[i]
        if mx >= 0 and mx < n and my >= 0 and my < n:
            if graph[mx][my] == 1 and visit[mx][my] == 0:
                visit[mx][my] = 1
                ans = dfs(mx, my, ans + 1)
    return ans

def solution(graph, n):
    answer = [0]
    count = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1 and visit[i][j] == 0:
                visit[i][j] = 1
                count.append(dfs(i, j, 1))
                answer[0] += 1
    count = sorted(count)
    answer.extend(count)
    for i in range(len(answer)):
        print(answer[i])


solution(graph, n)

---

실수 및 배운 점

• bfs에서는 deque 활용, 방향 설정을 내가 알기 쉽게 설정하자.

• dfs에서 return값을 어떻게 잡아야할지 감이 안섰다.
  global로 dfs에 접근할 때마다 카운트하려 했으나 가능한 쓰지 않는게 좋다길래,,
  함수 내에서 해결하기로 했다.

• dfs에서 ans값을 어떻게 이리저리 하면 되지 않을까하고 고민했다.
  dfs에 들어갈 때마다 ans += 1 해주고 나올 때 ans 값을 리턴했다.
  조금 헷갈렸지만.. 생각하다보니 이게 맞는 것 같다.