📌 문제 탐색하기
👉 문제바로가기
T: 테스트 케이스 개수
M: 배추밭의 가로 길이(1 ≤ M ≤ 50)
N: 배추밭의 세로 길이(1 ≤ N ≤ 50)
K: 배추가 심어져 있는 위치의 개수(1 ≤ K ≤ 2500)
K줄에 배추의 위치X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.
배추가 심어져 있는 위치를 입력받고, 땅의 처음부터 끝까지 탐색하면서 정점의 개수를 찾는 문제입니다. 한 정점에 대해 탐색을 수행하면서 값이 1인 곳(배추가 심어져 있는 곳)의 방문 여부를 True로 변경시켜주면 됩니다.
1️⃣ 입력 및 변수 정의
M, N, K = map(int, sys.stdin.readline().split())
arr = [[0] * M for _ in range(N)] # 배추의 위치
visited = [[False] * M for _ in range(N)]
count = 0 # 정점의 갯수2️⃣ 배추의 위치 설정
for _ in range(K):
X, Y = map(int, sys.stdin.readline().split())
arr[Y][X] = 13️⃣ 위치 탐색
for i in range(N):
for j in range(M):
if not visited[i][j] and arr[i][j] == 1:
count += 1
dfs(i, j) 땅의 처음부터 끝까지 모두 탐색하면서 dfs()를 호출합니다. 한 번의 정점을 기준으로 탐색하고, 해당 탐색이 끝나면 다음 칸을 정점으로 잡고 다시 탐색합니다. 하나의 정점에 대해 탐색이 끝난 경우 배추흰지렁이는 더이상 이동할 수 있는 칸이 없으므로 1마리를 추가합니다. 정점의 갯수가 우리가 구하고자하는 배추흰지렁이의 수가 되는 것입니다.
4️⃣ DFS
def dfs(i, j):
visited[i][j] = True
# 아래쪽 탐색
if i + 1 < N and not visited[i + 1][j] and arr[i + 1][j] == 1:
dfs(i + 1, j)
# 위쪽 탐색
if i - 1 >= 0 and not visited[i - 1][j] and arr[i - 1][j] == 1:
dfs(i - 1, j)
# 오른쪽 탐색
if j + 1 < M and not visited[i][j + 1] and arr[i][j + 1] == 1:
dfs(i, j + 1)
# 왼쪽 탐색
if j - 1 >= 0 and not visited[i][j - 1] and arr[i][j - 1] == 1:
dfs(i, j - 1)
else:
return 한 정점을 기준으로 사방(오른쪽, 왼쪽, 위쪽, 아래쪽)에 배추가 더 있는지 모두 탐색해야합니다. 배추가 더 있는 경우 탐색을 이어서 더 진행해야하기 때문에 재귀함수를 사용합니다.
📌 알고리즘 선택
한 정점과 인접한 가능한 모든 노드를 탐색해야 하므로 DFS를 사용하였습니다.
시간복잡도
for루프가 중첩되어있는 부분에서 전체 탐색에 대한 시간복잡도는 O(N*M)이며, 각 위치에 대한 DFS의 시간복잡도는 O(N*M)입니다. 따라서 전체 시간복잡도는 O(N*M)입니다. N, M의 최댓값은 50이므로 약 2500회의 연산이 수행됩니다. 이는 주어진 제한시간 1초 안에 충분히 가능한 연산입니다.
📌 코드 설계하기
- T, M, N, K를 Input받고 배추가 심어져있는 위치는 K줄에 Input받습니다.
- 입력받은 배추의 위치 좌표에 1을 대입하여 리스트값을 변경합니다.
- 땅 위치의 처음부터 끝까지 탐색하며 정점의 갯수를 구합니다.
📌 시도회차 수정사항
1회차
테스트 케이스 개수를 고려하지 않았습니다.
2회차: 런타임 에러
런타임 에러란?
- 프로그램 실행 도중 비정상적으로 종료되는 것
런타임 에러의 이유
런타임 에러의 이유는 다양하지만.. 제가 작성한 코드에서의 런타임 에러 이유는 다음과 같습니다.
- 백준 채점 시스템에서 최대 재귀 깊이를 디폴트 값으로 1000으로 정해놓았습니다.
- 런타임 에러는 그 최대 깊이를 초과하여 재귀 호출을 하기 때문에 발생하는 것입니다.
해결방법
import sys
sys.setrecursionlimit(10000)위 코드를 사용하여 최대 재귀 깊이를 늘려주었습니다.
📌 정답 코드
import sys
sys.setrecursionlimit(10000)
def dfs(i, j):
visited[i][j] = True
# 아래쪽 탐색
if i + 1 < N and not visited[i + 1][j] and arr[i + 1][j] == 1:
dfs(i + 1, j)
# 위쪽 탐색
if i - 1 >= 0 and not visited[i - 1][j] and arr[i - 1][j] == 1:
dfs(i - 1, j)
# 오른쪽 탐색
if j + 1 < M and not visited[i][j + 1] and arr[i][j + 1] == 1:
dfs(i, j + 1)
# 왼쪽 탐색
if j - 1 >= 0 and not visited[i][j - 1] and arr[i][j - 1] == 1:
dfs(i, j - 1)
else:
return
T = int(sys.stdin.readline())
for _ in range(T):
M, N, K = map(int, sys.stdin.readline().split())
arr = [[0] * M for _ in range(N)] # 배추의 위치
visited = [[False] * M for _ in range(N)]
count = 0 # 정점의 갯수
# 배추의 위치 입력
for _ in range(K):
X, Y = map(int, sys.stdin.readline().split())
arr[Y][X] = 1
# 모든 위치를 탐색하며 DFS 호출
for i in range(N):
for j in range(M):
if not visited[i][j] and arr[i][j] == 1:
count += 1
dfs(i, j)
print(count)📌 다른 풀이
아래 코드는 BFS를 활용한 코드입니다. (출처: @why_dev_says_no)
import sys
T = int(sys.stdin.readline())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 2. 한 노드에서 BFS를 탐색하는 과정을 구현합니다.
def bfs(x, y):
queue = [(x, y)]
global board
board[x][y] = 0
while queue:
x, y = queue.pop()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= M or ny < 0 or ny >= N:
continue
if board[nx][ny] == 1:
board[nx][ny] = 0
queue.append((nx, ny))
# 1. 문제의 input을 받습니다.
for _ in range(T):
M, N, K = map(int, sys.stdin.readline().split())
board = [[0 for _ in range(N)] for _ in range(M)]
for _ in range(K):
x, y = map(int, sys.stdin.readline().split())
board[x][y] = 1
ans = 0
# 3. 문제의 배열에 대해 BFS 탐색을 진행하며 지렁이의 개수를 구합니다.
for x in range(M):
for y in range(N):
if board[x][y] == 1:
bfs(x, y)
ans += 1
print(ans)
