Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[BFS] 동일 SET 영역 구하기 본문

프로그래밍

[BFS] 동일 SET 영역 구하기

yesungcho 2024. 3. 17. 16:37

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

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

 

2667번: 단지번호붙이기

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

www.acmicpc.net

다행이 문제는 빠른 시간 내에 풀었지만, 나는 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번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

https://yscho.tistory.com/148

 

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

계속 DFS로 푸는게 익숙해서 BFS가 너무 어렵다.. 익숙해지자! 화이팅! https://www.acmicpc.net/problem/10026 풀이는 아래 분 및 다양한 블로그 포스팅들을 참고 https://www.youtube.com/watch?v=xzOEbKqQQC4&t=314s https://

yscho.tistory.com