본문 바로가기
백준

[백준] 1021번 : 유기농 배추 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

by 우당탕탕 개발자 2023. 7. 21.
728x90
반응형

 

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 

1. 문제 설명

2. 풀이과정

  1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
  2. 해당 문제는 BFS 알고리즘으로 해결할 수 있는데 이때 popleft() 함수를 사용하기 위해 deque 자료구조를 사용하고 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
  3. BFS 함수를 구현한다. def BFS(row, col)
  4. 테스트 케이스 횟수를 입력받는다. T = int(sys.stdin.readline())
  5. 테스트 케이스 횟수만큼 반복하며 각 결과를 출력한다. for i in range(T)
  6. 배추밭의 가로길이, 세로길이, 배추의 위치 개수를 입력받는다. M, N, K = map(int, sys.stdin.readline().split())
  7. 배추밭을 2차원 리스트로 구현하기 위해 리스트를 생성하고 graph = list()
  8. 세로길이만큼 가로길이의 리스트를 추가한다. for j in range(N): graph.append([0] * M)
  9. 배추 위치의 개수만큼 반복하며 for j in range(K)
  10. 배추의 위치를 입력받고 v1, v2 = map(int, sys.stdin.readline().split())
  11. 배추밭 리스트에 1로 표시해 준다. 이때 입력받은 배추의 위치는 가로 위치, 새로 위치 순으로 입력받기 때문에 행과 열의 위치를 고려하여 표시해줘야 한다. graph[v2][v1] = 1
  12. 배추별 인접한 배추가 있는지 확인하기 위해 상, 하, 좌, 우로 이동한 행과 열의 변환 값을 저장한다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  13. 필요한 지렁이의 개수를 저장할 변수를 생성하고 초기화한다. answer = 0
  14. 배추밭의 모든 위치를 탐색하며 for j in range(N): for k in range(M)
  15. 배추가 있는 위치를 발견하면 BFS 함수를 활용하여 인접한 배추를 찾아 지우고 BFS(j, k)
  16. 지렁이 개수를 1마리 증가시킨다. answer += 1
  17. 구한 지렁이 개수를 출력한다. print(answer)

BFS 함수 설명

  1. BFS 함수는 탐색 시작 위치의 행과 열의 값을 입력받는다. def BFS(row, col)
  2. 인접한 배추가 있는 위치를 저장할 deque 자료구조를 생성한다. queue = deque()
  3. 가장 먼저 입력받은 위치를 리스트로 추가한다. queue.append([row, col])
  4. 배추를 찾은 위치는 다시 0으로 바꿔주어 중복을 피한다. graph[row][col] = 0
  5. 인접한 배추가 없을 때까지 반복하며 while (queue)
  6. 배추 위치의 행과 열 값을 차례대로 가져온다. row, col = queue.popleft()
  7. 상, 하, 좌, 우 4방향을 탐색하며 for i in range(len(move))
  8. 탐색할 다음 위치 좌표를 저장한다. nextRow = row + move[i][0]  nextCol = col + move[i][1]
  9. 만약 다음 위치가 배추밭 안에 있고 아직 찾지 않은 배추의 위치라면 if (0 <= nextRow < N) and (0 <= nextCol < M) and (graph[nextRow][nextCol] == 1)
  10. 다음 위치를 탐색할 위치 deque에 추가한다. queue.append([nextRow, nextCol])
  11. 그리고 탐색을 했으므로 0으로 바꿔준다. graph[nextRow][nextCol] = 0
반응형

3. 소스코드

import sys
from collections import deque

def BFS(row, col):
    queue = deque()
    queue.append([row, col])
    graph[row][col] = 0

    while (queue):
        row, col = queue.popleft()

        for i in range(len(move)):
            nextRow = row + move[i][0]
            nextCol = col + move[i][1]

            if (0 <= nextRow < N) and (0 <= nextCol < M) and (graph[nextRow][nextCol] == 1):
                queue.append([nextRow, nextCol])
                graph[nextRow][nextCol] = 0

T= int(sys.stdin.readline())

for i in range(T):
    M, N, K = map(int, sys.stdin.readline().split())

    graph = list()
    for j in range(N):
        graph.append([0] * M)

    for j in range(K):
        v1, v2 = map(int, sys.stdin.readline().split())
        graph[v2][v1] = 1

    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    answer = 0
    for j in range(N):
        for k in range(M):
            if (graph[j][k] == 1):
                BFS(j, k)
                answer += 1

    print(answer)
728x90
반응형