[DFS] 백준 1012. 유기농 배추 (feat. return, 가로 세로)
그래프 탐색하면서 한 구역인 애들 묶으면 총 몇 구역인지 세는 문제다.
아 행렬 위치가 너무 헷갈린다. graph[x][y]랑 가로m, 세로n이 너무 헷갈려서 index에러 때문에 고생했다.
우선, 문제의 함정인 행과 열, 가로와 세로 에 대해서 서술하고, 왜 이 문제를 다른 분들의 답코드를 봤음에도 1시간 이상이 걸리며 return한테 혼쭐난 과정을 자세하게 풀어보겠다.
행과 열, 가로와 세로
matrix = [[a,b,c],[A,B,C]] 가 있다고 하자. 이 이차원 배열을 각각 다른 말로 표현해보겠다.
배열 표현하기
- 2행 3열의 배열
- 가로 길이 3, 세로 길이 2의 좌표
- 0 <= x <3, 0<=y <2 범위의 matrix[x][y]
- matrix = [[0] * 3 for _ in range( 2 )]
배열의 원소 표현하기
- 첫 번째 행 = matrix[0]
- 첫 번째 열 = matrix[i][0]
- 1행 1열 = (0, 0) = matrix[0][0]
변수와 행렬
- x번째 행, y번째 열 = (x, y) = matrix[x-1][y-1]
- x개의 행, y개의 열 = [[0] * x for _ in range( y )]
matrix[x][y]
즉, matrix라는 2차원 배열의 인덱스에서 첫 번째 들어오는 변수가 행의 위치를 지정하고, 두번째 괄호에 들어가는 변수가 열의 위치를 지정한다. 가로 세로는 가로가 행을 의미하고 세로가 열을 의미한다고 생각하기 쉬우나, 가로의 개수(길이)와 세로의 개수(길이)를 변수로 입력받게 될 경우 피상적인 느낌과 달리 가로는 열의 개수, 세로는 행의 개수를 의미한다.
가로 개수가 w, 세로 개수가 h 이라면 2차원 배열을 만들 때, 수평적으로 w만큼 확장하고 수직적으로 h만큼 확장해야 한다. 이를 for 반복문으로 풀어서 써보면 아래처럼 된다.
matrix = []
for i in range( h ):
lst = []
for j in range( w ):
lst.append(i) # 열 추가 (1차원 배열의 횡적 확장, 옆으로)
matrix.append(lst) # 행 추가 (2차원 배열의 종적 확장, 위로)
로 쓸 수 있다. 이를 요소별 값은 다르지만 형태적으로 동일하도록 한 줄에 표현해보면 아래처럼 쓸 수 있다.
matrix = [ [0] * w for _ in range( h ) ]
matrix = [ [0]* 가로 개수 for _ in range( 세로 개수 ) ]
matrix = [ [0]* column for _ in range( row ) ]
요약
열의 개수 c = 가로 w
행의 개수 r = 세로 h
[[0] * w for _ in range(h)]
[[0] * c for _ in range(r)]
핵심 구조
# 핵심 구조
t = int(input()) # 테스트 개수
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def DFS(x,y):
for i in range(4):
# 상하좌우
xx = x+dx[i]
yy = y+dy[i]
if 새로운 좌표가 그래프 범위 밖일 때:
밭 아니니까 나가
if graph[xx][yy] == 0 :
배추 없는 거니까 나가
# 밭 범위이고, 배추 있는거
graph[xx][yy] = 0
DFS(xx,yy)
for _ in range(t):
m, n, k = map(int, input().split())
graph = [[0]*m for _ in range(n)]
cnt = 0
# 배추 심기
for _ in range(k):
w,h = map(int, input().split())
graph[h][w] = 1
# DFS
for x in range(n):
for y in range(m):
if 배추 있으면:
DFS로 근처 탐색(x,y)
cnt +1씩 증가
print(cnt)상하 좌우를 탐색해야 하기에 새로운 xx 와 yy 좌표 값을 DFS 함수의 매개변수로 보낸다. 다만 새로운 좌표값이 그래프 인덱스 범위를 벗어날 수 있기에 예외 처리를 해야 한다. 맨 밑에서 3번째 줄의 탐색을 마치면, 인접 요소들을 다 돌아나와 def DFS 스택을 소진하고 온 것이므로, 한 구역 탐색을 마쳤다고 볼 수 있다. 따라서 이때 cnt +=1 해주면 최종적으로 몇 개의 구역(덩어리)인지 구할 수 있는 것이다.
반례와 return
눈여겨 볼 차이점은, DFS 선언 내부 구조이다.
1 try
새로 할당한 xx와 yy를 DFS에 돌리기 전에 검사한다. 조건에 걸리면 return을 통해 for를 빠져나간다. return 되지 않은 xx, yy에 대해서만 배추를 뽑고, DFS 탐색을 한다.
>>> 오답
2 try
DFS에 들어온 파라미터를 바로 검사한다. 새로 할당한 xx와 yy를 검증없이 DFS에 바로 태워도 되게 된다. 어차피 다음 DFS(xx,yy)에 진입하면 첫 줄에서 검증당하니까.
>>> 정답, 사실상 1try와 같아야 한다고 생각했는데 정답. 머리가 먼저냐 꼬리가 먼저냐라서 결과가 다르게 나오면 안된다.
3 try
>>> 역시나 정답, return False와 for문의 문제가 아니었다.
4 try (최종)
다른 분들 처럼 범위 밖을 if 로 빼내지 말고, 범위에 해당하는 것을 돌리면 xx(이동한 x)를 검사하냐 x(입력 x)를 검사하냐 차이가 없이 정답이었다. 그렇다면 검증 순서의 문제도 아니다. 남은 차이점은 왜 여집합에 대한 조건을 거냐, 그 집합의 범위를 거냐인데 왜 내 코드에선 정오답이 달라졌을까?
따라서 1try의 구조인 xx yy 범위 검사를 먼저 하는 것으로 순서를 유지하되 정답이 나와야 완벽하게 오답이었던 이유를 알 수 있기 때문에, 다시 시도해봤다. 결론은, return때문에 생기는 문제였다. xx를 검사하게 됐을 때 상하좌우 이동을 하는 for문 안에서 return을 써버리면 for문을 돌다 말고 범위 밖의 인덱스를 만났을 때 return이 되어 버리면 나머지 이동(ex.하좌우)에 대한 for문을 마치지 않고 함수를 빠져나가 버리는 것이다. 결론은 for 안에서 조건을 쓸 경우, return을 함부로 쓰면 안 된다. 반례고 자시고 네 방향 전부를 탐색을 하고 빠져나가야 되는데, 거짓 return 당해버린다.
x 입력값을 그대로 검사하는 것은 이미 네 방향 모두 DFS로 진입을 한 상태이기 때문에 return에 영향을 받지 않는데,
xx 에 대해서 검사를 하는 건, for를 다 못돈 상태이기 때문에 인접을 인접으로 인식을 못한다.
따라서, 이동할 xx에 대해서 이동 전에 범위 검사를 하고 싶다면 반례에 대해서는 return False가 아니라 pass를 써줘야 한다.
1 try에 빨간 글씨로 쓴,
" return으로 for를 빠져나간다" 는 말에 이상함을 느꼈다면,
이 구구절절을 다 보지 않아도 됐던 것 !!
최종 코드
import sys
# sys.stdin =open('in2.txt','rt')
input = sys.stdin.readline
sys.setrecursionlimit(10**6) # 재귀함수 깊이 제한 풀기
t = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def DFS(x,y):
for i in range(4):
xx = x+dx[i]
yy = y+dy[i]
if xx < 0 or yy < 0 or xx >= n or yy >= m or graph[xx][yy] == 0:
pass
else:
graph[xx][yy] = 0 # 위치가 중요, 헷갈림
DFS(xx,yy)
for _ in range(t):
m, n, k = map(int, input().split())
graph = [[0]*m for _ in range(n)]
cnt = 0
# 배추 심기
for _ in range(k):
r,c = map(int, input().split())
graph[c][r] = 1 # 왜 [c][r] 임??
# DFS
for x in range(n):
for y in range(m):
if graph[x][y] == 1:
graph[x][y] = 0
DFS(x,y)
cnt+=1
print(cnt)답이 나온다고 그냥 지나가지 않고, 이런 저런 상황 변수를 통제해가며 시도해봄으로써 완벽하게 이해할 수 있었다. - 뿌듯 - 💫