[Python] 백준 #2667- 단지번호붙이기

문제

---

 

2667번: 단지번호붙이기

코드

---

My answer

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

n=int(input())

graph=[input().rstrip() for _ in range(n)]
visit=[[0]*(n) for _ in range(n)]
direct=[[0,1],[0,-1],[1,0],[-1,0]]
answer=[]

def bfs(x,y):
    Q=deque()
    Q.append((x,y))
    visit[x][y]=1
    cnt=1
    
    while Q:
        x,y=Q.popleft()
        for i in range(4):
            n_x,n_y=x+direct[i][0],y+direct[i][1]
            if(0<=n_x<n and 0<=n_y<n):
                if(visit[n_x][n_y]==0 and graph[n_x][n_y]=='1'):
                    visit[n_x][n_y]=1
                    cnt+=1
                    Q.append((n_x,n_y))  
    return cnt

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

print(len(answer))
answer.sort()
for i in range(len(answer)):print(answer[i])

Another answer

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input())))

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


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
result = 0

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

풀이

---

나는 bfs로 문제를 해결했고, 단순한 bfs로 구조를 만든뒤에 for 문을 통해서 아직 방문하지않았고 아파트가 있는지점에 한해서 bfs를 실행시켰고, bfs 함수내에서 앞으로 진행할때마다 즉 방문할때마다 cnt를 올려주고  종료시 cnt를 반환하여 특정단지에 속하는 아파트의 갯수를 저장하였다. 

이 문제의 경우 bfs와 dfs모두로 풀 수 있을 것 같다.