단지번호붙이기

백준 2667

처음에는 DFS로 구현했었는데 메모리 초과가 나고 런타임 에러가 났다. 코드상의 문제일수도 있지만 대부분의 경우 BFS가 좀 더 효율적이므로 BFS로 구현했다.

from collections import deque
from collections import Counter

n = int(input())
home = [list(map(int, input())) for _ in range(n)]

queue = deque()
visited = [[0]*n for _ in range(n)]

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

def bfs(x,y, cnt):
#넘겨받은 좌표의 값에 카운트를 대입하고, BFS방식대로 큐에 넣고 방문처리해준다.
    home[x][y] = cnt
    queue.append((x,y))
    visited[x][y] = 1

    while queue:
        x,y = queue.popleft()
        #상,하,좌,우 검사
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            #범위를 넘지않고 값이 1이고 방문하지 않았다면
            if 0<=nx<n and 0<=ny<n and home[nx][ny]==1 and visited[nx][ny]==0:
            	#값을 넣어주고 큐에 넣고 방문처리.
                home[nx][ny] = cnt  
                queue.append((nx,ny))
                visited[nx][ny] = 1

#값이 1이고 방문하지 않았다면 카운트를 증가시키고 bfs를 호출한다.
cnt = 0
for i in range(n):
    for j in range(n):
        if home[i][j] == 1 and visited[i][j]==0:
            cnt += 1
            bfs(i,j, cnt)

# BFS연산이 모두 끝나고 0보다 큰 값만 새로운 리스트에 저장한다.            
p = []
for i in range(n):
    for j in range(n):
        if home[i][j] > 0:
            p.append(home[i][j])

print(cnt)
# Counter를 이용해 cnt값에 대한 빈도수를 구해주고 이를 오름차순 정렬 후 출력한다.
p = sorted(Counter(p).values())
for ele in p:
    print(ele)

BFS : 넘겨받은 좌표값을 큐에 넣어주고 방문처리. -> 큐가 비어있지 않을 동안 큐에서 pop해서 pop한 값에 대한 이웃을 검사. -> 방문하지 않았다면 큐에 넣고 방문처리.

출력하는 부분에서 Counter가 아닌 set을 사용할 수도 있다.

p = []
for i in range(n):
    for j in range(n):
        if home[i][j] > 0:
            p.append(home[i][j])

p2=[]
print(len(set(p)))
for ele in set(p):
    p2.append(p.count(ele))
p2.sort()
for ele in p2:
    print(ele)

set은 중복을 허용하지 않으므로, set(p)에 있는 원소를 p에서 카운트해서 p2리스트에 담은 후 정렬하고 출력한다.

collections 모듈의 Counter 클래스 사용법

21.07.01 다시 푼 결과
문제 조건 중 정렬해서 출력하는 것 빼먹지 말기

from collections import deque

n = int(input())
home = [list(map(int, input())) for _ in range(n)]

def bfs(x, y, home, visited, n):
    queue = deque()
    visited[x][y] = 1
    cnt = 1
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                if visited[nx][ny] == 0 and home[nx][ny] == 1:
                    visited[nx][ny] = 1
                    cnt += 1
                    queue.append((nx, ny))
    return cnt

visited = [[0]*n for _ in range(n)]
cnt = 0
ans = []
for i in range(n):
    for j in range(n):
        if home[i][j] == 1 and visited[i][j] == 0:
            ans.append(bfs(i, j, home, visited, n))
            cnt += 1
print(cnt)
ans.sort()
for ele in ans:
    print(ele)