2267 단지번호붙이기

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque

dx = [0,0,-1,1] # 상 하 좌 우
dy = [-1,1,0,0] # 상 하 좌 우

def BFS(graph,x,y):
    q = deque()
    q.append((y,x))
    graph[y][x] = 0
    houses = 1

    while q:
        y,x = q.popleft()

        for i in range(4):
            # 상 하 좌 우 탐색
            ny = y + dy[i]
            nx = x + dx[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if graph[ny][nx] == 1:
                graph[ny][nx] = 0
                q.append([ny, nx])
                houses +=1
    return houses

import sys
read = sys.stdin.readline
N = int(read())
graph = []

for i in range(N):
    # 숫자가 붙어있을땐 이렇게 해야하는 듯.
    graph.append(list(map(int,input())))


houses_list = []

for i in range(N): # y
    for j in range(N): # x
        y,x = i,j # 현재 위치
        if graph[y][x] == 1:
        # 방문하지 않은 집이고, graph를 보았을 때 집이라면 이것과 연결된 것들을 탐색해서(BFS발동) 번지수를 만들자.
            houses = BFS(graph,x,y)
            houses_list.append(houses)

houses_list.sort()
print(len(houses_list))
for m in houses_list:
    print(m)

3. 문제 풀이

이 문제 또한 미로찾는거랑 다를 바 없다. 근데 많은 사람들이 이런 문제를 풀 때 visited 그래프를 만들지 않고 입력 graph로만 처리한다. 그래서 나도 이런 부분은 배워야할 것 같다. 하루 이틀 해서 될 문제가 아니고 꾸준히 익혀야할 것 같다. 문제 풀이는 일반적인 BFS문제와 다를 바 없기 때문에 할 것은 없다ㅠ