[Python] 소프티어 LV.2_장애물 인식 프로그램

소프티어 LV.2_장애물 인식 프로그램

import sys
from collections import deque

#bfs
# 1인 값의 위치를 큐에 모두 넣는다.
# 큐에서 값을 하나씩 꺼내서 상하좌우가 1인 값을 탐색한다.
# 탐색할 때 방문처리 한다.
# 뭉탱이의 개수를 센다.
# 더이상 없으면 종료한다. 

n = int(sys.stdin.readline().rstrip())
maps = [sys.stdin.readline().rstrip() for _ in range(n)]

   

queue = deque([])
#북동남서
dx = [0, 1, 0, -1] #좌우
dy = [-1, 0, 1, 0] #상하
visited = [[0]*n for _ in range(n)]
cnt = 1

for i in range(n):
  for j in range(n):
    if maps[i][j] == '1' and visited[i][j] == 0:
      visited[i][j] = cnt
      queue.append([i, j])
      
      while queue:
        x, y = queue.popleft() #얜 이미 maps 값이 1인 애
        
        for k in range(4):
          nx, ny = x + dx[k], y + dy[k]
          if 0<= nx < n and 0<= ny < n and maps[nx][ny] == '1':
            if visited[nx][ny] == 0: #값이 1이고, 방문하지 않았다면
                visited[nx][ny] = cnt
                queue.append([nx, ny])

      cnt += 1


#visited에서 가장 큰 수 출력
#visited에서 각 수의 개수 출력 - dict이용

max_value = 0
result = {}
for i in range(n):
  for j in range(n):
    max_value = max(max_value, visited[i][j])
    if visited[i][j] > 0:
      if visited[i][j] in result:
        result[visited[i][j]] += 1
      else:
        result[visited[i][j]] = 1

result = sorted(result.items(), key=lambda x : x[1])

print(max_value)
for i in range(len(result)):
  print(result[i][1])