[baekjoon] 백준 1012번 : 유기농 배추 (by python 파이썬) bfs 너비우선 탐색

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

1012번: 유기농 배추

 

정답 code

t = int(input())
dx = [1,-1,0,0] #x축이동
dy = [0,0,-1,1] #y축이동

def bfs(x, y):
    queue = [[x, y]]
    while queue:
        a, b = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4): #좌우상하 검색
            q = a + dx[i]
            w = b + dy[i]
            if 0 <= q < n and 0 <= w < m and land[q][w] == 1: #땅을 안벗어나고 배추가 심어져있을때
                land[q][w] = 0 #0으로 바꿔줌
                queue.append([q, w])

for _ in range(t):
    m, n, k = map(int,input().split())
    land = [[0]*m for _ in range(n)]
    count = 0
    print(land)
    for _ in range(k):
        a, b = map(int,input().split())
        land[b][a] = 1

    for j in range(n):
        for k in range(m):
            if land[j][k] == 1:
                bfs(j,k)
                land[j][k] = 0
                count += 1
    
    print(count)

 

이번문제는 처음에 이해를 아예 잘못해서 문제풀이에 어려움이 있었다.

 

조건이 배추에서 인접배추로 상하좌우관계에 있을때 지렁이가 이동 가능한데 이걸 한단계만 가능하다고 생각하여 

문제가 원하는 조건과 아예 다르고 다루기 훨씬 까다로웠다.

 

하지만 문제가 원하는 조건은 상하좌우 관계에서 지렁이는 배추가 있으면 계속 움직일 수 있기에 bfs(너비우선 탐색)   방식으로 해결 하는 방법을 선택했다.

 

soultion

1. 땅 크기만큼 0으로 초기화시킴

2. 입력받은 배추 위치를 1로 변경

3. 순차탐색으로 땅을 탐색하며 배추가 있으면 bfs함수로 인접 배추를 구해줌

      1. 해당 땅의 좌표를 큐에 삽입

      2. 변수값에 넣고 큐 삭제.

      3. 해당 변수값의 땅의 상하좌우를 탐색후 땅크기를 안벗어나고 해당 위치에 배추가 있다면,

         해당 땅의 값을 0으로 바꾸고 해당 땅 좌표를 큐에 삽입

      4. 큐의 값이 없을때까지 계속 탐색

4. 해당 땅의 값 0으로 교체

5. 해당땅에 지렁이가 이동할 수 있는 배추의 모든 경우를 제거 했음으로 count변수 1추가

6. count = 지렁이 값 출력

 

 

+ bfs에 대한 설명

https://freedeveloper.tistory.com/373

[이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘