[Softeer] 장애물 인식 프로그램

https://softeer.ai/practice/info.do?idx=1&eid=409 

Softeer

문제 해결

백준에서 많이 풀었던 문제라 코드는 빨리 짰는데 board 입력을 str으로 받아놓고 계속 비교를 0으로 하니까 답이 안나오지..

 

간단한 bfs 문제여서 visited로 확인한 자리인지 체크만 해주면서 1일 때 카운트해주고 그 값만 마지막에 넘겨주면 되는 문제 !

코드

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

N = int(input())
board = []
for i in range(N):
    board.append(list(input().strip()))

visited = [[0]*N for _ in range(N)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
result = []

def solution(x , y):
    q = deque()
    q.append([x,y])
    visited[x][y] = True
    cnt = 1

    while q:
        x,y = q.popleft()

        for d in range(4):
            next_x = x + dx[d]
            next_y = y + dy[d]

            if  (0 <= next_x < N and 0 <= next_y < N) and (visited[next_x][next_y] == False) and board[next_x][next_y] == '1':
                q.append([next_x, next_y])
                visited[next_x][next_y] = True
                cnt += 1
        
    return cnt

for i in range(N):
    for j in range(N):
        if (board[i][j] == '1') and visited[i][j] == False:
            result.append(solution(i,j))

result.sort()
print(len(result))
for r in result:
    print(r)