[코드트리 챌린지] 5주차 (10/4-10/9), DFS

진단 결과

이번엔 과연 백트래킹 늪에서 탈출할 수 있을까 떨리는 마음으로 아침에 일어나자마자 경건한 마음으로 실력진단을 해보았다.

그 결과..

 

 

 

610 -> 645

점수가 상승했다!!

백트래킹 늪 탈출!!!

역시 성장은 계단형이라고 했던가..🥹

 

 

 

 

 

 

드디어 기본 4문제를 다 푸는 쾌거를..!

기본 4문제를 다 푸니까 갑자기 문제가 한 10개..?가 뒤에 추가되는 걸 보았다..

뭔가 이제 시작인가..하는 마음으로 새로 추가된 문제를 풀어보려고 했는데 뭔가 풀 수 있을 것만 같은 간단한 문제로 보였다

근데 문제만 간단한 거였을까.. 백트래킹에서 착안한 아이디어로 visited함수를 사용해서 풀어보기도하고,, 보다보니 오?이거 BFS아닌가?라는 생각이 들었지만 결국엔 풀지 못했다.

그렇게 결과에서는 오른쪽 사진에서 볼 수 있다시피 바로 "dfs, bfs에 대한 학습이 필요해요"라는 진단을 받았따,,

하지만, 점수가 올랐다는 기쁨이 더 커서 이제는 공부해서 풀면 되지!라는 자신감으로 패기롭게 학습을 시작하게 되었다

 

학습 전략

이번 주 내 학습 전략은 '차근히 순차적으로' 였다

일단 진단 결과에서 바로 INTERMEDIATE LOW -> DFS에서 개념들을 설명해주는 페이지로 넘어갔다.

하지만, DFS, BFS를 학부 때 배웠지만 기억 속에 희미한 나는 NOVICE HIGH->그래프탐색 카테고리에서 DFS를 하기 전 개념들을 학습하는 것이 우선이었다.

DFS에 필요한 선수 개념 학습 완료!

 

개인적으로 DFS는 나에게 어려운 영역이었기 때문에 pseudo code부터 완전한 코드까지 도출해내는 과정이 필요했다.

아래는 코드트리 설명에서 제공해준 DFS 탐색에 대한 코드이다.

# pseudo code
function dfs(pos)
	visit(pos)
        for children of pos
            if visited[child] == false
                dfs(child)
            
# DFS 탐색 - 인접행렬
def dfs(vertex):
	for curr_v in range(1, VERTEXS_NUM + 1):
            if(graph[vertex][curr_v] and not visited[curr_v]):
                print(curr_v)
                visited[curr_v] = True
                dfs(curr_v)
                
# DFS 탐색 - 인접리스트
def dfs(vertex):
	for curr_v in graph[vertex]:
            if not visited[curr_v]:
                print(curr_v)
                visited[curr_v] = True
                dfs(curr_v)

포인트는 재귀함수이다.

왜냐하면, 백트래킹처럼 그래프에서 더 깊이 못들어가면 나와야하기 때문이다.

탐색을 하면서 연결이 되어있고, 방문하지 않았으면 들어가도록 하는 것이다.

이 대개념을 입력한 채 문제를 풀어보겠다.

 

풀어본 문제

# 두 방향 탈출 가능 여부 판별하기

코테 공부를 조금만이라도 해봤던 사람은 이 문제 형식과 비슷한 문제들을 엄청나게 많이 봤을 것이다.

이 문제를 가져온 이유는 그 중 한명이었던 내가 어떻게 이 문제를 풀게 되는지 과정을 보여주기 위해서이다.

n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 아래와 오른쪽 2방향 중 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 <그림 1>과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요.

풀이 전략

1. n*m 그리드 범위 안에 있기

2. 뱀이 없는 자리

3. 방문하지 않았던 자리

일단 DFS로 풀어야겠다는 전략이 수립됐다면, 위 3가지 조건에 맞는 곳을 다녀가면 된다.

 

위 문제를 풀기 위해선 결론은 하나만 알면된다.

'끝점을 방문했나?'

이 결론에 같이 도달했다면 출력은 visited[끝][점]을 해주면된다.

 

해당 문제를 내가 푼 코드는 아래와 같다.

n, m = tuple(map(int, input().split()))

arr = [
    list(map(int, input().split()))
    for _ in range(n)
]
visited=[
    [0 for _ in range(m)] 
    for _ in range(n)
]
dxs, dys = [1,0],[0,1]

def in_range(x, y):
    if x<0 or x>=n or y<0 or y>=m:
        return False
    if arr[x][y]==0 or visited[x][y]==1:
        return False

    return True

def dfs(x,y):
    for dx, dy in zip(dxs, dys):
        new_x = x + dx
        new_y = y + dy
        if in_range(new_x, new_y):
            visited[new_x][new_y] = 1
            dfs(new_x, new_y)

dfs(0,0)
print(visited[n-1][m-1])

 

이 문제 이렇게 설명하면 DFS개념 알고~ 후딱 솨라락! 푼 거 같아보이지만, 고비가 많았다.

왼쪽 사진은 모두 내가 제출했던 결과이다.

이렇게 계~~~속 런타임에러가 발생했었다.

놀랍게도 코드를 보면 볼 수록 틀린 게 없는 것 같았는데 런타임에러가 나왔다.

이유는 너무 어이가 없었다.

런타임에러 로직이 너무 과하게 돌아가도 나지만, 내 경험상 범위가 맞지 않아도 나는 경우를 종종 봤다.

x<0 or x>=n or y<0 or y>=m

문제는 그리드 범위 안에 해당되는지 검토하던 함수 내용 중 이 부분에 있었다.

에러가 나는 코드 안에서는 아래처럼 m과 n을 거꾸로 작성했다.

x<0 or x>=m or y<0 or y>=n

n*m 그리드이면 n행이기 때문에 y점과 n이 연관된다고 생각했었는데, 지금 생각하니 나 스스로 너무 꼬아서 생각하고 있었다. 멍청,,

 

DFS 예전부터 나한텐 너무 어려운 거라고 지레 겁먹었었는데 이렇게 차근히 푸니까 풀리는 이 성취감을 느낄 수 있어서 너무 뿌듯하다.

난이도 낮은 문제위주로 풀었었는데 고난도 문제들에 도전해봐야겠다!