99클럽 코테 스터디 9일차 TIL / BFS(너비 우선 탐색)

✏️ 문제

https://www.acmicpc.net/problem/7562

 

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S1

✅ 소요 시간: 28분 44초

✅ 권장 시간: 1시간

 

💡 풀이

1) 문제 유형 파악

문제에 주어진 그림과 최소 이동 횟수를 구해야 하는 걸 보고 BFS로 풀어야겠다고 생각했다.

 

2) 아이디어 흐름

① 나이트가 움직일 수 있는 방향 표현

지금까지 본 BFS 문제들은 항상 뭔가를 2차원 리스트 위에서 움직여 답을 찾는 방식이었다. 이 문제도 그 틀에서 벗어나진 않지만 단순히 상하좌우로 움직이는 게 아니기 때문에 dx, dy 배열을 만들 때 값을 잘 입력해주는 게 중요하다.

 

총 여덟 방향으로 움직일 수 있고 이동 가능한 방향은 (-2, -1, 1, 2)를 조합해 표현할 수 있다.

 

② 이동 횟수 계산

❎ move 변수 활용

첫 번째 시도는 이동 횟수를 저장하기 위한 변수 'move'를 0으로 초기화하고 체스판 영역 안에 있는 칸에 대해 특정 칸이 아직 방문하지 않은 상태일 때마다 move += 1을 수행하는 것이었다.

 

이 방식을 쓰니까 최소 이동 횟수를 구할 수가 없었다. 코드에서 아래 위치에 print문을 추가하고 이동 횟수가 어떻게 출력되는지 확인해봤다.

 

 

 

시작 좌표를 (0, 0) / 목표 좌표를 (7, 0)으로 주고 코드를 돌린 후 순서대로 출력된 세 줄이다. 두 번째 줄을 보면 (0, 0)에서 (2, 1)은 나이트의 움직임 특성상 한 번 만에 갈 수 있음에도 불구하고 이동 횟수는 2번으로 나오고 있다. 세 번째 경우도 마찬가지!

 

출발점 좌표를 (x, y)라고 할 때 (x+dx[i], y+dy[i])까지의 최소 이동 횟수는 맨 처음 출발 좌표에서부터 누적으로 구하는 게 아니라 (x, y)를 기준으로 처리하는 과정이 필요해보인다.

 

✅ visited 리스트 활용

첫 번째 시도에서 파악한 문제점을 해결하기 위해 visited 리스트의 형식을 살짝 변형했다. 2차원 리스트 형식인 건 동일하지만 모든 값을 0으로 초기화하고 i행 j열에는 시작점에서 i행 j열까지 오기 위해 필요한 최소 이동 횟수를 저장해주는 것이다.

 

이 때 시작점에서 시작점까지는 이동할 필요가 없지만 구현 편의를 위해 visited[시작점 x 좌표][시작점 y 좌표] 값은 1로 초기화했다.

 

이 방식을 이용한다면 (x, y)에서 (x+dx[i], y+dy[i])까지 오기 위한 최소 이동 횟수는 visited[x+dx[i]][y+dy[i]] = visited[x][y]+1로 표현할 수 있다.

 

③ 정답 출력

출발점의 초기 값이 1이었기 때문에 정답을 구할 때는 visited[타겟 x 좌표][타겟 y 좌표]-1로 계산해줘야 한다.

 

3) 구현

from collections import deque

T = int(input())

for _ in range(T):
    L = int(input())
    
    s_x, s_y = map(int, input().split())
    t_x, t_y = map(int, input().split())
    
    queue = deque([(s_x, s_y)])
    
    visited = [[0]*(L+1) for _ in range(L+1)]
    
    visited[s_x][s_y] = 1
    
    dx = [-2, -2, -1, -1, 1, 1, 2, 2]
    dy = [-1, 1, -2, 2, -2, 2, -1, 1]
    
    while queue:
        r, c = queue.popleft()
        
        if r == t_x and c == t_y:
            break
        
        for i in range(8):
            nr, nc = r+dx[i], c+dy[i]
            
            if (0 <= nr < L and 0 <= nc < L) and not visited[nr][nc]:
                visited[nr][nc] = visited[r][c]+1
                
                queue.append((nr, nc))

    print(visited[t_x][t_y]-1)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 처음에 이동 횟수를 카운트 하는 부분에서 조금 헛다리 짚긴 했지만 금방 수정했고 그 외에 어려운 점은 없었다.

❗ 배운 점

• 오늘은 배운 점이라기보다 그냥 내 생각 정리? - 다른 유형의 문제보다 BFS/DFS 문제 TIL을 작성할 때 내가 이해한 게 맞나? 이렇게 표현하면 다른 사람들이 잘 알아 들을 수 있을까? 하는 생각이 유독 많이 든다. 문제를 많이 풀어보고, 풀이를 많이 적어보는 방법 밖에는 없겠지 🔥