[Baekjoon] 2667번 : 단지번호붙이기 (Python)

[Baekjoon] 2667번 : 단지번호붙이기 (Python)

 

목차

 

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

2667번: 단지번호붙이기

Python

 

방법 1 - 메모리 31084KB / 시간 72ms / 코드 길이 702B/596B

 

DFS를 활용한 방법

global cnt를 활용하여 각 단지 내 집의 수를 센다.

나머지는 일반적인 DFS와 같다.

 

n = int(input())
l = []
for i in range(n):
     l.append(list(map(int, input())))

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

visit = [[0]*n for _ in range(n)]

def dfs(x, y):
    if x < 0 or x > n-1 or y < 0 or y > n-1:
        return False

    if visit[x][y] == 0 and l[x][y] == 1:
        visit[x][y] = 1
        global cnt
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

res=[]
cnt = 0

for i in range(n):
    for j in range(n):
        if visit[i][j] == 0 and l[i][j] == 1:
            dfs(i, j)
            res.append(cnt)
            cnt = 0

print(len(res))
res.sort()
for x in res:
    print(x)

 

 

n = int(input())
l = []
for i in range(n):
     l.append(list(map(int, input())))

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

def dfs(x, y):
    if x < 0 or x > n-1 or y < 0 or y > n-1:
        return False

    if l[x][y] == 1:
        global cnt
        cnt += 1
        l[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

res=[]
cnt = 0

for i in range(n):
    for j in range(n):
        if dfs(i, j):
            res.append(cnt)
            cnt = 0

res.sort()
print(len(res))
for x in res:
    print(x)

 

방법 2 - 메모리 32436KB / 시간 88ms / 코드 길이 762B

 

BFS를 활용하는 방법

주의) deque() 후 append를 진행해야 함. deque((x,y))를 한다면 

TypeError: cannot unpack non-iterable int object Error를 만남

 

from collections import deque

n = int(input())
l = []
for i in range(n):
     l.append(list(map(int, input())))

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

def bfs(x, y):
    n = len(l)
    queue = deque()
    queue.append((x,y))
    cnt = 1
    l[x][y] = 0

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
                continue

            if l[nx][ny] == 1:
                queue.append((nx, ny))
                l[nx][ny] = 0
                cnt += 1
    return cnt

res=[]

for i in range(n):
    for j in range(n):
        if l[i][j]:
            res.append(bfs(i,j))

res.sort()
print(len(res))
for x in res:
    print(x)