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

 

🔗 2667. 단지번호 붙이기 - 백준 

 

📌오늘의 학습 키워드

• BFS인거 같은데

✨공부한 내용 본인의 언어로 정리하기

• dx,dy 에서 배운것도 써봤다. 어제 visited를 사용하지 않았었는데 이번에는 사용해 봤다.

📚오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  • 오늘은 냅다 코드를 적지 않고 구성을 하고 진행해 봤다. 역시 훨씬 수월했다.
• 어떻게 해결했는지
  • 각 집을 순회하면서 만약 집이 있으면 그 집 근처의 이웃들을 모두 찾는 방식으로 해결했다.

[🤓문제 해결 코드]

import sys
from collections import deque

n = int(sys.stdin.readline())
board = []
visited = []

for _ in range(n):
    nums = sys.stdin.readline().strip()
    num_list = []
    for num in nums:
        num_list.append(int(num))
    board.append(num_list)
    visited.append([0 for _ in range(n)])

villages = []

mapper = {
    0: (1, 0),
    1: (0, 1),
    2: (-1, 0),
    3: (0, -1)
}


def in_range(x, y):
    return 0 <= x < n and 0 <= y < n


def find_neighbor(row, col):
    deq = deque()
    deq.append([row, col])
    count = 1
    while deq:
        n_row, n_col = deq.popleft()
        for d in range(4):
            m_row, m_col = mapper[d]
            new_row, new_col = n_row + m_row, n_col + m_col
            if in_range(new_row, new_col) and not visited[new_row][new_col] and board[new_row][new_col]:
                count += 1
                visited[new_row][new_col] = 1
                deq.append([new_row, new_col])
    villages.append(count)


# 판에 모든 숫자 순회
for row in range(n):
    for col in range(n):
        if board[row][col] and not visited[row][col]:
            visited[row][col] = 1
            find_neighbor(row, col)

print(len(villages))
villages.sort()
for i in villages:
    print(i)