S1 2667. 단지번호붙이기

문제 보기 :  2667번: 단지번호붙이기 (acmicpc.net)

---

문제

• 정답률 : 42%

---

작성 코드 & 풀이 과정 코멘트

from collections import deque

def solution(graph,start):
    graph[start[0]][start[1]]= 0 
    direction = [(-1,0),(1,0),(0,-1),(0,1)]
    count = 1
    dd = deque([start])
    while dd:
        x,y = dd.popleft()
        for dx,dy in direction:
            xx = dx+x ; yy = dy+y
            if 0<=xx<n and 0<=yy<n and graph[xx][yy]==1:
                graph[xx][yy]=0
                count += 1
                dd.append((xx,yy))
    return count

n = int(input())
graph = [list(map(int,list(input()))) for _ in range(n)]
answer = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            answer.append(solution(graph,(i,j)))

print(len(answer))
for i in sorted(answer):
    print(i)

graph에서 1인 지점 좌표를 (i,j)로 두는데 이걸 start로 하는데, 이를 input로 받는 def를 짜야한다.
BFS 알고리즘으로 해결했다.

첫 시작 지점은 0으로 변경 후 시작한다.

direction으로 현위치 상하좌우를 확인하는데, 그래프 노드가 1이면 dd에 추가하고 그 확인 지점은 0으로 변경한다. 
단지 안에 몇 아파트가 있는지 확인하기 위해 count를 두었는데, 한 턴을 돌 때마다 이 값에 1을 더한다. 
dd가 빈 deque가 된다면 끝내면 된다.