# 문제 https://www.acmicpc.net/problem/1012
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
# 나의 풀이
전에 풀었던 Number of Island와 같은 문제다 그래프의 너비우선탐색 (bfs) 와 깊이우선탐색(dfs)를 다시 상기하는 마음으로 풀었다.
가장 기본적인 그래프 문제이다.
배추 밭을 묵시적 그래프로 생각하여 그래프 순회 알고리즘을 이용하는 접근 방식을 가져야 한다.
적용할 수 있는 그래프 알고리즘 2개
1. 너비 우선 탐색의 핵심은 파이썬의 덱(dequeue)를 이용하여 근처 그래프의 탐색 예약을 통해 푼다.
2. 깊이 우선 탐색의 핵심은 함수의 재귀를 이용하여 푸는 방식이다.
이 문제는 상하좌우 4방향 탐색으로 탐색한 곳을 visited 2차원 리스트에 표시하며 탐색한다. 반복문을 돌 때 방문한적 없고, 배추가 있는 곳은 너비우선탐색 또는 깊이우선탐색을 시작하여 방문 한 곳을 visited 리스트에 표시한다. 탐색할 때 마다 필요한 벌레 수를 증가시키며 모든 그래프를 순회 한다.
최종 제출 한 코드
# BFS 너비 우선 탐색
from collections import deque
t = int ( input ())
# 가로 m (c)
# 세로 n (r)
while t > 0 :
m , n , k = map ( int , input (). split ())
ground = [[ 0 ] * (m) for _ in range ( n )]
visited = [[ False ] * (m) for _ in range ( n )]
for i in range ( k ):
c , r = map ( int , input (). split ())
ground [ r ][ c ] = 1
bug = 0
def bfs ( r , c ):
visited [ r ][ c ] = True
queue = deque ()
queue . append (( r , c ))
dy = [ 1 , - 1 , 0 , 0 ]
dx = [ 0 , 0 , - 1 , 1 ]
while queue :
cur_r , cur_c = queue . popleft ()
for i in range ( 4 ):
next_r = cur_r + dy [ i ]
next_c = cur_c + dx [ i ]
if next_r >= 0 and next_r < n and next_c >= 0 and next_c < m :
if visited [ next_r ][ next_c ] != True and ground [ next_r ][ next_c ] == 1 :
visited [ next_r ][ next_c ] = True
queue . append (( next_r , next_c ))
for r in range ( n ):
for c in range ( m ):
if ground [ r ][ c ] == 1 and not visited [ r ][ c ]:
bfs ( r , c )
bug += 1
print ( bug )
t -= 1
개인적으로 재귀를 푸는 dfs 보다 bfs가 익숙하며, 실수할 일이 적었다.
순회하는 리스트의 인덱스의 경계값을 잘 확인하며 코드를 작성해야 한다.
# dfs (테스트 케이스 통과, 제출 시 런타임 오류 발생)
t = int ( input ())
while t > 0 :
m , n , k = map ( int , input (). split ())
ground = [[ 0 ] * (m) for _ in range ( n )]
visited = [[ False ] * (m) for _ in range ( n )]
for i in range ( k ):
c , r = map ( int , input (). split ())
ground [ r ][ c ] = 1
bug = 0
def dfs ( r , c ):
visited [ r ][ c ] = True
if r + 1 < n and not visited [ r + 1 ][ c ] and ground [ r + 1 ][ c ] == 1 :
dfs ( r + 1 , c )
if c + 1 < m and not visited [ r ][ c + 1 ] and ground [ r ][ c + 1 ] == 1 :
dfs ( r , c + 1 )
if r - 1 >= 0 and not visited [ r - 1 ][ c ] and ground [ r - 1 ][ c ] == 1 :
dfs ( r - 1 , c )
if c - 1 >= 0 and not visited [ r ][ c - 1 ] and ground [ r ][ c - 1 ] == 1 :
dfs ( r , c - 1 )
for r in range ( n ):
for c in range ( m ):
if ground [ r ][ c ] == 1 and not visited [ r ][ c ]:
dfs ( r , c )
bug += 1
print ( bug )
t -= 1
테스트 케이스는 통과하였지만 어딘가 부족하다.
if 문이 4번이나 반복하는 코드를 구현 하였고, 더욱 간결하게 코드를 수정해야한다.
런타임 오류가 발생하는 이유를 아직 찾지 못했다, 아마 인덱스 초과 오류일 가능성이 크다고 추측했다.
런타임 에러 이유
import sys
sys . setrecursionlimit ( 10 ** 6 )
함수 탐색 깊이 제한을 풀어 주어 해결하였다.
# DFS 최종 제출 코드
import sys
sys . setrecursionlimit ( 10 ** 6 )
t = int ( input ())
while t > 0 :
m , n , k = map ( int , input (). split ())
ground = [[ 0 ] * (m) for _ in range ( n )]
visited = [[ False ] * (m) for _ in range ( n )]
for i in range ( k ):
c , r = map ( int , input (). split ())
ground [ r ][ c ] = 1
bug = 0
def dfs ( r , c ):
visited [ r ][ c ] = True
delta = [( 1 , 0 ),( 0 , 1 ),( - 1 , 0 ),( 0 , - 1 )]
for dy , dx in delta :
nr , nc = r + dy , c + dx
if 0 <= nr < n and 0 <= nc < m and not visited [ nr ][ nc ] and ground [ nr ][ nc ] == 1 :
dfs ( nr , nc )
for r in range ( n ):
for c in range ( m ):
if ground [ r ][ c ] == 1 and not visited [ r ][ c ]:
dfs ( r , c )
bug += 1
print ( bug )
t -= 1
배울 수 있었던 것
1. 아는 문제여도 꼼꼼히 신중하게 접근 해야한다. 너무 자만하지 말 것
2. BFS 보다 DFS 가 상대적으로 실력이 부족하다. 재귀 함수 혹은 DFS 문제를 더 많이 풀어 보아야 겠다.
