728x90
반응형
1. 문제 설명
2. 풀이과정
- sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
- 해당 문제는 BFS 알고리즘으로 해결할 수 있는데 이때 popleft() 함수를 사용하기 위해 deque 자료구조를 사용하고 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
- BFS 함수를 구현한다. def BFS(row, col)
- 테스트 케이스 횟수를 입력받는다. T = int(sys.stdin.readline())
- 테스트 케이스 횟수만큼 반복하며 각 결과를 출력한다. for i in range(T)
- 배추밭의 가로길이, 세로길이, 배추의 위치 개수를 입력받는다. M, N, K = map(int, sys.stdin.readline().split())
- 배추밭을 2차원 리스트로 구현하기 위해 리스트를 생성하고 graph = list()
- 세로길이만큼 가로길이의 리스트를 추가한다. for j in range(N): graph.append([0] * M)
- 배추 위치의 개수만큼 반복하며 for j in range(K)
- 배추의 위치를 입력받고 v1, v2 = map(int, sys.stdin.readline().split())
- 배추밭 리스트에 1로 표시해 준다. 이때 입력받은 배추의 위치는 가로 위치, 새로 위치 순으로 입력받기 때문에 행과 열의 위치를 고려하여 표시해줘야 한다. 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)
- 배추가 있는 위치를 발견하면 BFS 함수를 활용하여 인접한 배추를 찾아 지우고 BFS(j, k)
- 지렁이 개수를 1마리 증가시킨다. answer += 1
- 구한 지렁이 개수를 출력한다. print(answer)
BFS 함수 설명
- BFS 함수는 탐색 시작 위치의 행과 열의 값을 입력받는다. def BFS(row, col)
- 인접한 배추가 있는 위치를 저장할 deque 자료구조를 생성한다. queue = deque()
- 가장 먼저 입력받은 위치를 리스트로 추가한다. queue.append([row, col])
- 배추를 찾은 위치는 다시 0으로 바꿔주어 중복을 피한다. graph[row][col] = 0
- 인접한 배추가 없을 때까지 반복하며 while (queue)
- 배추 위치의 행과 열 값을 차례대로 가져온다. row, col = queue.popleft()
- 상, 하, 좌, 우 4방향을 탐색하며 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)
- 다음 위치를 탐색할 위치 deque에 추가한다. queue.append([nextRow, nextCol])
- 그리고 탐색을 했으므로 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
반응형
'백준' 카테고리의 다른 글
[백준] 2579번 : 계단 오르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.25 |
---|---|
[백준] 10814번 : 나이순 정렬 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.24 |
[백준] 1149번 : RGB거리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.23 |
[백준] 10773번 : 제로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.21 |
[백준] 11726번 : 2xn 타일링 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.20 |
[백준] 7568번 : 덩치 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.20 |
[백준] 2581번 : 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.17 |
[백준] 11650번 : 좌표 정렬하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.17 |