[항해99] 99클럽 코테 스터디 9일차 TIL + (BFS 백준 7562 나이트의 이동)

99클럽 코테 스터디 9일차 TIL + 오늘의 학습 키워드(BFS 백준 7562 나이트의 이동)

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

1. 오늘의 학습 키워드

• BFS
• 백준 7562 나이트의 이동
• 2차원 배열에서의 최단 경로 탐색

2. 공부한 내용

# 나이트가 이동할 수 있는 8가지 방향을 정의
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

def BFS(start_x, start_y, destination_x, destination_y, I):
    queue = deque()
    queue.append((start_x, start_y))
    # 체스판 크기만큼의 2차원 배열 생성
    graph = [[0] * I for _ in range(I)]
    # 시작 위치 방문 표시
    graph[start_x][start_y] = 1
    
    while queue:
        x, y = queue.popleft()
        # 목적지에 도달하면 이동 횟수 반환
        if x == destination_x and y == destination_y:
            return graph[x][y] - 1
            
        # 8가지 방향에 대해 이동 가능한지 확인
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # 체스판 범위 내이고 아직 방문하지 않은 곳이라면
            if 0 <= nx < I and 0 <= ny < I and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1  # 이동 횟수 증가
                queue.append((nx, ny))

2.1 BFS 구현 포인트

• deque를 사용하여 효율적 큐 구현
• 2차원 배열을 사용하여 방문 여부와 이동 횟수를 동시에 체크
• 나이트의 이동 방향을 dx, dy로 표현
• 최단 경로를 찾기 위해 BFS 활용

3. 오늘의 회고

아직은 BFS, DFS 문제 풀이가 익숙치가 않다. BFS, DFS 문제라고 생각되면 기본 양식(?) queue, 함수 등을 일반적으로 구현해놓고 문제에 맞게 설계하는 능력이 필요할 것 같다. 나이트의 이동은 [-1, 2]와  같이 지금까지 풀었던 [0, 1], [1, 0] 등과 같은 형태가 아니었는데 혼동했었다. 방문 체크와 이동 횟수를 어떻게 동시에 관리할 것인지와 같이 내가 지금 고려해야 하는게 어떤 것인지에 대해 정확하게 인지하는게 필요하다. 결론은 아직 BFS, DFS가 익숙하지가 않다는 것...