[BOJ] Python 백준 1012번 유기농 배추 실버 2

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

1012번: 유기농 배추

문제 풀이

---

문제에서도 한눈에 알 수 있듯이 그래프 탐색을 하는 문제다.

 

문제를 간략하게 다시 설명하자면 0은 비어있는 땅, 1은 배추가 있는 땅이고 각 케이스마다 배추가 이어져있는 구역을 세서 출력하면 된다.

 

그래프를 탐색하는 방법은 스택을 쓰는지, 큐를 쓰는지에 따라 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)으로 나뉘는데 둘 다 시간 복잡도는 비슷하므로 편한 방식으로 구현하면 된다.

 

필자는 최단 거리를 찾을 때 BFS가 유리하므로 보통 BFS로 구현한다.

 

바로 전체 코드를 확인해 보자.

 

testcase=int(input())
dir=[[-1,0],[0,1],[1,0],[0,-1]]
for i in range(testcase):
    queue=[]
    res=0
    M,N,K=map(int,input().split())
    graph=[[0 for j in range(M)]for k in range(N)]
    for j in range(K):
        tempm,tempn=map(int,input().split())
        graph[tempn][tempm]=1
    for j in range(N):
        for k in range(M):
            if graph[j][k]==1:
                res+=1
                queue.append([j,k])
                graph[j][k]=0
                while len(queue)>0:
                    tempn,tempm=queue.pop(0)
                    for a in range(len(dir)):
                        dx=tempn+dir[a][0]
                        dy=tempm+dir[a][1]
                        if 0<=dx<N and 0<=dy<M and graph[dx][dy]==1:
                            graph[dx][dy]=0
                            queue.append([dx,dy])
    print(res)

 

1번째 줄은 테스트 케이스만큼 반복하기 위한 변수이고 2번째 줄은 각 노드에서 탐색 방향(위, 오른쪽, 아래, 왼쪽)을 묶어놓은 리스트이다.

 

이렇게 방향을 리스트로 묶으면 4가지 방향을 탐색할 때 반복문으로 해결할 수 있다는 장점이 있기에 꼭 잊지 말길 바란다.

 

대부분은 4가지 방향이지만 가끔 대각선도 고려하는 8가지 방향 문제도 있는데 단순하게 방향을 고려해서 8개의 리스트를 넣으면 된다.

 

4번째 줄의 queue는 큐를 사용함으로써 BFS 방식을 쓰기 위해 선언한 리스트이다.

 

가끔 리스트를 큐 방식으로 쓸 때 시간 초과가 나는 경우가 있는데 이는 pop() 함수에서 마지막 원소부터 탐색하기 때문에 첫 번째 원소를 제거하기 위해서는 O(n)의 시간 복잡도가 걸리기 때문이다.

 

그럴 경우엔 deque 모듈을 사용하면 O(1)로 첫 번째 원소에 삽입하고 삭제할 수 있다.

 

8번째 줄은 배추의 위치를 갱신하는 반복문이고 11번째 줄부터는 그래프를 전체 탐색하면서 배추 구역을 카운트하는 반복문이다.

 

13번째 줄은 배추가 있을 경우 카운트를 하고 인접한 배추 구역을 0으로 바꾸는 작업이다.

 

보통 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없어서 아예 0으로 바꿨다.

 

또한 20, 21번째 줄에서 탐색할 노드의 위치를 계산하여 따로 변수에 저장하는 이유는 미리 값을 저장해놔야 그래프 크기 안인지 배추가 있는 노드인지 체크할 때 불필요한 연산 횟수를 줄일 수 있기 때문에 값을 저장하는 것을 추천한다.

 

결과 화면

 

탐색 방향을 고려할 필요도 없고 단지 구역만 세면 되기 때문에 그래프 문제 중에서도 꽤 쉬운 편에 속한다고 생각한다.