📌 문제 : 백준 1012번
📌 문제 탐색하기
T : 테스트케이스 수
M : 배추밭 가로 길이 (1 ≤ M ≤ 50)
N : 배추밭 세로 길이 (1 ≤ N ≤ 50)
K : 배추 위치 개수 (1 ≤ K ≤ 2500)
X : 배추의 가로 위치 (0 ≤ X ≤ M-1)
Y : 배추의 세로 위치 (0 ≤ Y ≤ N-1)
✅ 입력 조건
1.T입력
2.M,N,K공백 구분해 입력
3.K번 반복해 배추 위치 입력
4. 배추 위치가 같은 경우 ❌
5.0→ 배추 ❌,1→ 배추 ⭕️
✅ 출력 조건
1. 필요한 최소 배추흰지렁이 마리 수 출력
2. 배추 모인 곳에 배추흰지렁이 1마리 필요 → 배추 영역 세서 출력
배추흰지렁이의 최소 마리 수를 출력하는 문제이다.
어떤 배추에 배추흰지렁이 1마리가 있다면 인접 배추도 보호를 받을 수 있고, 인접한다는 것은 배추의 상하좌우에 배추가 위치함을 의미한다.
즉, 배추가 모여 있는 지역의 수를 출력하면 된다.
백준에서 재귀 깊이 관련해 에러가 발생하는 경우가 있어서 BFS를 사용하려고 한다.
N*M의 땅에서 배추가 있는 땅을 의미하는 1을 가지고 있는 위치이면 BFS를 수행하도록 조건문을 작성한다.
collections 라이브러리의 deque를 호출한다.
BFS는 큐를 이용해 인접 노드를 반복적으로 큐에 넣도록 알고리즘을 구현한다.
해당 위치에서 상하좌우로 이동해서 배추가 있는 땅인지 확인해야 하므로 4가지 방향으로 이동할 수 있도록 이동 방법을 정의해준다.
for문을 통해 4가지 방향으로 이동했을 때
1) N*M내에 있으면서,
2) 배추가 있는 땅인지 확인하고
조건에 맞다면 탐색하도록 구현한다.
테스트케이스 T만큼 반복해서 M, N, K 입력를 받는다.
위치를 저장할 그래프를 N*M 크기로 만들고 0으로 채운다.
K만큼 반복해서 배추 위치 X, Y를 반복해서 받아 해당 위치의 그래프 값에 1을 저장한다.
입력받은 그래프를 이중 for문으로 돌면서 배추 있는 땅이라면 BFS를 수행한다.
방문 처리 리스트를 따로 정의하지 않고, 방문한 위치 값을 0으로 바꾸어 방문 처리해준다.
가능한 시간복잡도
그래프 저장 →
N*M 내에서 BFS 수행 →
최종 시간복잡도
테스트케이스 수까지 고려하면 으로,
최악의 경우, M과 N이 최대 50일 때
이 되어 1초 내로 계산이 가능할 것 같다.
알고리즘 선택
그래프에 배추 위치 입력받고 전체 배추 영역을 돌면서 조건에 따라 BFS 수행하기
📌 코드 설계하기
- 배추 확인 위해 4가지 방향 이동 방법 정의
- BFS 정의
2-1. 방문 처리
2-2. 4가지 방향 이동
2-3. 영역 내에 있는 배추가 있는 땅이면서 방문하지 않은 땅이 있으면 탐색 - 테스트케이스 T 입력
- 테스트케이스 만큼 반복
4-1. M, N, K 입력
4-2. K번 반복해 배추 위치 X, Y 입력
4-3. 배추흰지렁이 셀 변수 정의
4-4. N*M에서 BFS 수행
4-5. T개 정답 저장 - 원하는 형식으로 출력
📌 시도 회차 수정 사항
1회차
# 4-2. K번 반복해 배추 위치 X, Y 입력
graph = [[0] * N for _ in range(M)]
for _ in range(K):
x, y = map(int, input().split())
graph[x][y] = 1
# 4-3. 배추흰지렁이 셀 변수 정의
count = 0
# 4-4. N*M에서 BFS 수행
for i in range(M):
for j in range(N):
if graph[i][j] == 1:
bfs(i, j)
count += 1- 결과
- 들여쓰기를 잘못해서 K번 입력받을 때마다 BFS를 실행하게 되었다.
# 4-2. K번 반복해 배추 위치 X, Y 입력
graph = [[0] * N for _ in range(M)]
for _ in range(K):
x, y = map(int, input().split())
graph[x][y] = 1
# 4-3. 배추흰지렁이 셀 변수 정의
count = 0
# 4-4. N*M에서 BFS 수행
for i in range(M):
for j in range(N):
if graph[i][j] == 1:
bfs(i, j)
count += 1
# 4-5. T개의 정답 저장
answer.append(count)- 들여쓰기를 수정했다.
2회차
# 2-2. 4가지 방향 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 2-3. 영역 내에 있는 배추가 있는 땅이면서 방문하지 않은 땅이 있으면 탐색
if 0 <= nx < M and 0 <= ny < N and graph[x][y] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))- 결과
- BFS를 통해 인접한 모든 배추들을 찾은 후에 count가 1 증가해야 하는데 K값 그대로 나오고 있다.
# 2-2. 4가지 방향 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 2-3. 영역 내에 있는 배추가 있는 땅이면서 방문하지 않은 땅이 있으면 탐색
if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))- 방문하지 않은 땅이 있으면 탐색하는 부분에서 이동한 후의 위치에 대해서 방문 여부를 확인해야 하는데
graph[x][y]로 하는 바람에 잘못된 조건으로 탐색하게 되었다. graph[nx][ny]으로 수정했더니 제대로 작동하였다.
📌 정답 코드
import sys
from collections import deque
input = sys.stdin.readline
# 1. 배추 확인 위해 4가지 방향 이동 방법 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 2. BFS 정의
def bfs(x, y):
queue = deque([(x, y)])
# 2-1. 방문 처리
graph[x][y] = 0
while queue:
x, y = queue.popleft()
# 2-2. 4가지 방향 이동
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 2-3. 영역 내에 있는 배추가 있는 땅이면서 방문하지 않은 땅이 있으면 탐색
if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))
# 정답 저장 리스트
answer = []
# 3. 테스트케이스 T 입력
T = int(input())
# 4. 테스트케이스 만큼 반복
for _ in range(T):
# 4-1. M, N, K 입력
M, N, K = map(int, input().split())
# 4-2. K번 반복해 배추 위치 X, Y 입력
graph = [[0] * N for _ in range(M)]
for _ in range(K):
x, y = map(int, input().split())
graph[x][y] = 1
# 4-3. 배추흰지렁이 셀 변수 정의
count = 0
# 4-4. N*M에서 BFS 수행
for i in range(M):
for j in range(N):
if graph[i][j] == 1:
bfs(i, j)
count += 1
# 4-5. T개의 정답 저장
answer.append(count)
# 5. 원하는 형식으로 출력
for count in answer:
print(count)- 결과
📌 회고
- 코드가 길어지니 계속 실수가 생긴다.
