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

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

2667번: 단지번호붙이기

 

 

아 한 번에 푼 문제 완전 오랜만이라 신난다.

bfs로 풀 수 있는 문제인데 그러면 기존에 푼 dxdy 문제랑 코드가 같아서 dfs로 풀었다. 뭐 물론.. 큰 차이는 없다. 그냥 deque를 안 쓴 것 뿐.. ㅋㅋㅋㅋ

 

input 0110100을 받는다고 가정했을 때, 이를 개별 int로 받는 과정을 생각하는 게 어려웠다.

list(map(int, input().split()))으로 했더니 그냥 110100이라는 수로 입력을 받더라고..

이 부분 좀 더 연습해야지.

 

def dfs(x, y):
    global count
    count += 1
    visited[x][y] = 1
    dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dx, dy in dxdy:
        new_x = x + dx
        new_y = y + dy
        if -1 < new_x < len(town) and -1 < new_y < len(town[0]):
            if not visited[new_x][new_y] and town[new_x][new_y] == 1:
                dfs(new_x, new_y)

n = int(input())
town = [[] for i in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
apt = []

for i in range(n):
    line = list(input())
    for j in range(len(line)):
        line[j] = int(line[j])
    town[i] += line

count = 0
for i in range(n):
    for j in range(n):
        if town[i][j] == 1 and not visited[i][j]:
            dfs(i, j)
            apt.append(count)
            count = 0

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

 

 

---

 

 

#220126

풀땐 몰랐는데 전에 푼 위에 코드를 보니 숫자 입력받는 부분에서 엄청 애를 먹었더라고..

지금은 한 줄이면 되는데 저 때는 이중 for문 돌려서 한 걸 보며 안쓰러웠다..

 

나머지는 어렵지 않았는데 자꾸 에러가 나서

bfs 함수 안에서 not visited[nx][ny]를 visited[nx][ny] == 1 로 바꿔주었더니 성공했다.

 

둘의 차이를 알아보려 질문했는데 not visited[nx][ny]로 해도 잘 된다고 하셔서 ??? 상태가 되었다.

다시 해봤는데 잘 되더라고....? 귀신이 곡할 노릇.

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bfs(x, y):
    global cnt
    cnt += 1
    visited[x][y] = 1
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < n and -1 < ny < n:
                if map[nx][ny] == 1 and visited[nx][ny] == 0: #not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                    cnt += 1

n = int(input())
map = [list(map(int, input().strip())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
cnt = 0
town = []

for i in range(n):
    for j in range(n):
        if map[i][j] == 1 and not visited[i][j]:
            bfs(i, j)
            town.append(cnt)
            cnt = 0
            
print(len(town))
for i in sorted(town):
    print(i)

 

난리났다.