(Python/🥈1)백준 알고리즘 2667번: 단지번호붙이기

728x90

문제출처: https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

풀이:

틀린코드

import sys
from collections import deque

N = int(input())

def bfs(x,y):
    count = 0
    queue =deque([(x,y)])
    while queue:
        a, b = queue.popleft()
        for next_x, next_y in move:
            nx ,ny = a + next_x,  b + next_y
            if N > nx >= 0 and N > ny >= 0 and visited[nx][ny] == -1 and map[nx][ny] == 1:
                visited[nx][ny] = 0
                queue.append((nx,ny))
                count += 1
    return count


visited = [[-1] * N for _ in range(N)] # 밟은 땅 확인
move = [(1,0),( -1,0),(0,-1),(0,1)] #상,하,좌,우
map = [list(map(int,input())) for i in range(N)] # 예제 입력
res= []
block = 0
for x in range(len(map)):
    for y in range(len(map)):
        if visited[x][y] == -1 and map[x][y] == 1:
            res.append(bfs(x,y))
            block += 1
res.sort()
print(block)
for i in res:
    print(i)

눈으로 본 정답은 맞는데 돌리면 틀린다. 이유를 몰라 visited 를 없애고 풀었다.

정답코드.

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


N = int(input())

def bfs(map,x,y):
    queue =deque([(x,y)])
    map[x][y] = 0
    count = 1
    while queue:
        a, b = queue.popleft()
        for next_x, next_y in move:
            nx ,ny = a + next_x,  b + next_y
            if N > nx >= 0 and N > ny >= 0 and map[nx][ny] == 1:
                map[nx][ny] = 0
                queue.append((nx,ny))
                count += 1
    return count


move = [(1,0),( -1,0),(0,-1),(0,1)] #상,하,좌,우
map = [list(map(int,input())) for i in range(N)] # 예제 입력
res= []
block = 0
for x in range(len(map)):
    for y in range(len(map)):
        if map[x][y] == 1:
            count = bfs(map,x,y)
            res.append(count)
            block += 1
res.sort()
print(block)
for i in res:
    print(i)