224. 단지번호붙이기

백준




1.Python


정해



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

n = int(input())
graph = [list(input().rstrip()) for _ in range(n)]

count = []

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

def bfs(x, y):
  q = deque()
  q.append((x, y))
  graph[x][y] = '0'
  cnt = 0
  while q:
    x, y = q.popleft()
    cnt += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == '1':
        q.append((nx, ny))
        graph[nx][ny] = '0'
        

  count.append(cnt)

result = 0

for i in range(n):
  for j in range(n):
    if graph[i][j] == '1':
      bfs(i, j)
      result += 1

print(result)

count.sort()

for a in count:
  print(a)


  • bfs 처음에 graph[x][y] = '0'을 빼먹었었다..!!!


틀렸습니다


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

n = int(input())
graph = [list(input().rstrip()) for _ in range(n)]

count = []

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

def bfs(x, y):
  q = deque()
  q.append((x, y))
  cnt = 0
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == '1':
        q.append((nx, ny))
        graph[nx][ny] = '0'
        cnt += 1

  count.append(cnt)

result = 0

for i in range(n):
  for j in range(n):
    if graph[i][j] == '1':
      bfs(i, j)
      result += 1

print(result)

count.sort()

for a in count:
  print(a)

좋은 웹페이지 즐겨찾기