[BFS] 동일 SET 영역 구하기

적록색약 문제와 같이 비슷한 유형의 문제를 풀어보았다.

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

2667번: 단지번호붙이기

다행이 문제는 빠른 시간 내에 풀었지만, 나는 set 별로 coloring을 해준 다음에 갯수를 count해서 그다지 갯수를 세는 데에 효율적인 코딩은 아니었던 거 같다. 

처음 통과 코드

from collections import deque

N = int(input())

maps = [ [int(x) for x in input()] for _ in range(N)]

visited = [ [0]*N for _ in range(N) ]

def BFS(maps,queue) :
    while queue :
        x, y = queue.popleft()

        for i in range(4) :
            after_x = x+move_x[i]
            after_y = y+move_y[i]

            if after_x < 0 or after_y < 0 or after_x >= N or after_y >= N :
                continue

            if visited[after_x][after_y] == 0 and maps[after_x][after_y] == 1 :
                queue.append([after_x,after_y])
                visited[after_x][after_y] = visited[x][y]
                

move_x = [1,-1,0,0]
move_y = [0,0,1,-1]

CLASS = 1
for i in range(N) :
    queue = deque()
    for j in range(N) :
        if maps[i][j] == 1 and visited[i][j] == 0 :
            queue.append([i,j])
            visited[i][j] = CLASS
            BFS(maps,queue)
            CLASS += 1

print(CLASS-1)
count = []
for now in range(1,CLASS) :
    cnt = 0
    for i in range(N) :
        for j in range(N) :
            if visited[i][j] == now :
                cnt += 1
    count.append(cnt)

for final_cnt in sorted(count) :
    print(final_cnt)

 

밑에 count세는 게 너무 바보 같이 구현한거 같은데... 방문했던 곳을 0으로 만들어버려서 쉽게 구현하신 분도 계셨다. 

참고해서 구현한 코드. 시간도 더 빨랐고... 코드도 더 readable했다.

from collections import deque

N = int(input())

maps = [ [int(x) for x in input()] for _ in range(N)]

counts = []

def BFS(maps,queue) :
    count = 1
    while queue :
        x, y = queue.popleft()

        for i in range(4) :
            after_x = x+move_x[i]
            after_y = y+move_y[i]

            if after_x < 0 or after_y < 0 or after_x >= N or after_y >= N :
                continue

            if maps[after_x][after_y] == 1 :
                queue.append([after_x,after_y])
                maps[after_x][after_y] = 0
                count += 1
    counts.append(count)
                
move_x = [1,-1,0,0]
move_y = [0,0,1,-1]

cnt = 0
for i in range(N) :
    queue = deque()
    for j in range(N) :
        if maps[i][j] == 1 :
            queue.append([i,j])
            maps[i][j] = 0
            BFS(maps,queue)
            cnt += 1

print(cnt)
counts.sort()

for answer in counts : 
    print(answer)

 

 

참고로 적록색약도 전에 공부했던 중요한 유형이므로 공부하자

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

10026번: 적록색약

https://yscho.tistory.com/148

[코딩테스트] BFS 보다 더 익숙해지기