이것이 코딩테스트다: 음료수 얼려먹기
교재와 다른 풀이 방법
교재에서는 dx, dy 테크닉을 사용하지 않고 갈 수 있는 곳의 좌표를 재귀를 통해 탐색했으나
dx, dy 테크닉을 사용해서 풀이했습니다.
정답 코드
def dfs(x, y):
graph[x][y] = -1
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if (0 <= nx < n) and (0 <= ny < m):
if graph[nx][ny] == 0:
graph[nx][ny] = -1
dfs(nx, ny)
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
dfs(i, j)
cnt += 1
print(cnt)풀이 과정
DFS로 풀이를 하겠다는 생각이 들어서 바로 풀이를 시도하였습니다.
풀이 이후 답안 코드를 보니 위에서 말했듯이 dx, dy 테크닉을 사용하지 않는 풀이였기에 지금 이 방법대로 풀었습니다.
dx, dy라는 리스트를 생성해서 값을 지정해줍니다.
저 값은 상하좌우를 뜻하며 좌표계 방식이 아니라 행렬 방식으로 이루어집니다.
처음 dx, dy 테크닉을 사용할 때 저 -1, 1, 0, 0을 이해하지못했었는데 이해를 하고 풀이를 하셔야합니다.
graph 입력의 경우 리스트 컴프리헨션 방식으로 입력을 받습니다.
이중 for문을 돌면서 그래프의 값들을 탐색하면서 순회를 시작합니다.
이 문제의 경우 0으로 이루어진 구간이 몇개인지를 추출하는 문제입니다.
그랬기에 순회를 돌며 값이 0이라면 dfs 함수로 들어가게 됩니다.
dfs안에서는 dx, dy를 사용해서 상하좌우로 각각 값들을 비교합니다.
비교를 하는데 단 해당 그래프를 초과하게 될시 out of range 오류가 날 수 있으니 if문을 통해서 범위를 잡습니다.
그 후 graph의 값이 0이라면 그 구간을 -1로 변경한 뒤 다시 dfs로 재귀를 탑니다.
-1로 바꿔주는 이유는 0과 1로 이루어져있는데 방문을 했음을 의미하기 위해서 이미 체크한 부분을 -1로 체크합니다.
그러면 0이 아닌 다른 값이기 때문에 탐색에서 제외됩니다.
그렇게 0을 상하좌우로 돌면서 dfs를 반복하는데 상하좌우 모두 0이 없는 경우
0이 모인 구간에서 제외되었다는 것을 뜻하며 그때 cnt += 1을 통해 구간의 개수가 추가됩니다.
문제점
계속 범위 초과 에러가 나서 코드를 재차 디버깅했습니다.
if (0 <= nx < n) and (0 <= ny < m):
if graph[nx][ny] == 0:
graph[nx][ny] = -1
dfs(nx, ny)이 범위구간을 n과 m을 잘못 기입하여서 범위 오류가 났었습니다.
print문을 찍어보면서 오류를 찾는 방법은 역시 유용한 것 같습니다.
