[BOJ] 2667 python

* DFS 가 BFS 보다 편한지 정답코드 DFS가 많았다.

 

BFS 로 풀었고,

완전히 내것으로 만드는데는 아직..

 

그래도 신박했던 부분은,

이 부분.

 

만들어 놓은 graph를 모두 방문해주되, 1이 있는 graph의 좌표의 경우에만 bfs 를 실행해준다.

그게 코드로, 

 

for i in range(N):

    for j in range(N):

         if graph[i][j] == 1:

              cnt.append(bfs(i,j)) # bfs 에서 1인 해당 좌표를 탐색해줘!

 

아래는 bfs로 푼 전체 코드이다. 

from collections import deque
import sys
input=sys.stdin.readline

def bfs(a,b):
    cnt=1
    q=deque()
    q.append((a,b))
    graph[a][b] = 0

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

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
                cnt+=1
    return cnt

N=int(input())
cnt=[]
graph=[]
for i in range(N):
    graph.append(list(map(int, input().rstrip()))) # 단지 설정
for i in range(N):
    for j in range(N):
        if graph[i][j]==1:
            cnt.append(bfs(i,j)) # 모든 그래프를 모두 방문해주되, 1이 있으면 bfs실행
print(len(cnt))
cnt.sort()
for i in range(len(cnt)):
    print(cnt[i])