[알고리즘] 백준 1926번 Python

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

BFS 유형의 문제는 여러가지 유형이 존재한다.

 

가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 

주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다.

 

이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것  같다.

 

문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다.

 

BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다.

 

1. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다.
2. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다.
3. 각각의 BFS를 동시에 진행하되 서로에게는 큰 영향이 없다.
4. 각각의 BFS를 동시에 진행하면서 영향마저 존재 한다.
5. 각각의 BFS에서 탐색한 형태를 기억해야한다.

 

이 문제는 1번에 해당해서 그냥 그래프에서 1에 해당하는 경우마다 BFS를 수행하고

적절하게 몇번째 BFS인지, 해당 BFS에서 탐색한 1로 이루어진 그래프의 크기는 무엇인지만 체크하면 된다.

 

그러나 4,5와 같은 유형은 난이도가 높다고 생각하며 2,3역시 처음에 접하면 접근이 쉽지는 않다고 생각한다.

 

5번은 BFS를 이용해서 최단경로를 구하는데, 최단경로가 여러개인 경우 각각을 기억해서 추가적인

문제 풀이가 필요한 경우이다.

 

 

일단 BFS문제를 열심히 풀고 각각 유형별로 세부 분류를 해보려고 한다.

 

그리고 1번 유형이어도 3차원 BFS를 사용해야 하는 경우도 처음 접하면 풀기가 힘들다고 생각한다.

 

 

---

 

내가 작성한 코드

 

정답을 받음

 

import sys
from collections import deque

N, M = map(int, input().split())


graph = []

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


que = deque()

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))


maxSize = 0
count = 0

def BFS(n, m):
    size = 1
    global que
    que.append((n,m))
    graph[n][m] = 2

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

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

            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 1:
                    graph[ny][nx] = 2
                    que.append((ny,nx))
                    size += 1
    return size



for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            count += 1
            maxSize = max(maxSize,BFS(i,j))

print(count)
print(maxSize)

 

---

풀어보면 좋은 문제들 

(바킹독님 문제집)

 

https://www.acmicpc.net/workbook/view/7313

문제집: 0x09강 - BFS (BaaaaaaaaaaarkingDog)

 

 

참고

---

바킹독님 강의

https://www.youtube.com/watch?v=ftOmGdm95XI