[코드트리] 코딩테스트 벼락치기를 위한 갭체크 진단 후기

코딩테스트를 도전한지 벌써 몇년이 지났다. 

몇년동안 작심 삼일을 몇번이나 했던가... 

 

올해는 꾸준히 해보자고 다짐하기도 n번째, 코드트리 청약 통장 챌린지를 알게되었다. 

 

내가 부족한 부분을 알 수 있는 갭체크를 해보았다.

너무 급하게 풀었는지,,,막상 진단 결과를 보니 내가 부족한 부분은 완전탐색 III와 BFS 쪽이었다.

처음에는 “BFS를 헷갈려한다”라고만 생각했는데, 다시 문제를 풀어보니 정확히는 BFS 자체보다도 그 전에 필요한 기본 구현에서 많이 흔들렸다. 특히 격자에서 이동할 때 사용하는 방향 배열을 항상 헷갈려했다. 

BFS는 큐를 이용해서 가까운 위치부터 차례대로 탐색하는 알고리즘이다. 하지만 격자 문제에서는 BFS를 쓰기 전에 먼저 “어느 방향으로 이동할 수 있는지”를 코드로 표현해야 한다. 이때 사용하는 것이 dx, dy 배열이다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

위 코드는 상하좌우 이동을 의미한다.

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

 

이렇게 작성하면 현재 위치 (x, y)에서 다음 위치 (nx, ny)를 계산할 수 있다. 처음에는 이 구조가 익숙하지 않아서 매번 if문으로 방향을 나눠야 하나 고민했는데, 방향 배열을 사용하면 이동 로직을 반복문으로 간단하게 처리할 수 있다는 점을 다시 정리했다.

다만 여기서 한 가지 더 헷갈렸던 부분은 대각선 이동이었다. 상하좌우 이동과 대각선 이동은 방향 배열이 다르다. 예를 들어 대각선 네 방향은 다음과 같이 따로 정의해야 한다.

ddx = [-1, -1, 1, 1]
ddy = [-1, 1, -1, 1]

 

실제로 문제를 풀 때 이 부분을 잘못 작성해서 대각선 이동 배열을 이상하게 한 적이 있었다. 코드 전체 흐름은 맞았지만 방향 배열 하나가 틀리니 결과도 당연히 틀렸다. 이 경험을 통해 BFS나 완전탐색 문제에서는 알고리즘 개념뿐만 아니라, 이동 방향을 정확히 정의하는 기본 구현도 중요하다는 것을 느꼈다.

또 하나 인상 깊었던 부분은 방문 배열이었다. 단순한 BFS 문제에서는 보통 visited[x][y]처럼 2차원 방문 배열을 사용한다. 하지만 대각선 이동을 최대 3번까지 사용할 수 있는 문제에서는 같은 칸에 도착하더라도 대각선을 몇 번 사용했는지에 따라 이후에 갈 수 있는 경로가 달라진다.

그래서 이 경우에는 다음처럼 3차원 방문 배열을 사용해야 했다.

visited = [[[-1] * 4 for _ in range(N)] for _ in range(N)]

 

처음에는 왜 방문 배열이 3차원이어야 하는지 이해가 잘 안 됐다. 하지만 같은 위치라도 “대각선을 0번 사용해서 도착한 상태”와 “대각선을 3번 모두 사용해서 도착한 상태”는 이후 선택지가 다르다는 것을 알게 되었다. 즉, BFS에서는 단순히 칸을 방문했는지만 보는 것이 아니라, 문제에 따라 어떤 상태로 방문했는지를 함께 저장해야 한다.

이번 갭체크를 통해 내가 보완해야 할 부분은 단순히 어려운 알고리즘을 외우는 것이 아니라, 격자 탐색 문제의 기본 구조를 정확히 익히는 것이라고 느꼈다. 특히 다음과 같은 부분을 더 연습해야겠다고 생각했다.

1. dx, dy 방향 배열을 사용해 상하좌우 이동 구현하기
2. 대각선 이동이 필요한 경우 별도의 방향 배열 만들기
3. 이동 후 격자 범위를 벗어나는지 확인하기
4. BFS에서 큐를 사용해 현재 위치와 상태를 함께 관리하기
5. 문제 조건에 따라 visited 배열을 2차원 또는 3차원으로 설계하기

아래는 이번에 다시 정리한 BFS 기본 구조이다.

 

from collections import deque

queue = deque()
queue.append((0, 0))
visited[0][0] = 1

while queue:
    x, y = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            if not visited[nx][ny]:
                visited[nx][ny] = 1
                queue.append((nx, ny))

 

이 구조를 정확히 이해하면 미로 탐색, 최단 거리, 격자 이동, 방문 횟수 계산 같은 문제로 확장할 수 있다. 아직은 문제를 보면 바로 BFS 구조가 떠오르지 않고, dx, dy부터 헷갈리는 단계지만, 이번 갭체크를 통해 내가 어떤 부분에서 막히는지 명확히 알 수 있었다.

앞으로는 코드트리에서 BFS와 완전탐색 문제를 풀 때 정답 여부만 확인하지 않고, 막히는 부분을 잘 정리해보려 한다. 

 

이번 학습을 통해 느낀 점은, 쉬운 문제처럼 보여도 기본 구현이 흔들리면 계속 오답이 나온다는 것이다. 특히 BFS는 개념 자체도 중요하지만, 실제 코드에서는 dx/dy, queue, visited, 범위 체크가 함께 맞물려야 제대로 동작한다.

그래서 이번 코드트리 청약 통장 챌린지 기간에는 BFS, DFS를 중심으로 풀어보려고 한다. 단순히 문제 수를 채우기보다, 내가 헷갈렸던 구현 패턴을 하나씩 정리하면서 코딩테스트 감각을 다시 회복하는 것이 목표다.

 

코드트리에서 직접 갭체크와 알고리즘 학습을 해보고 싶다면 여기에서 확인할 수 있다.