99클럽 코테 스터디 9일차 TIL + BFS(C++)

문제

[백준] 7562번: 나이트의 이동

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

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int T;
int l;
int now_x, now_y;
int target_x, target_y;

int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};

void bfs(int start_x, int start_y) {
    vector<vector<int>> visited(l, vector<int>(l, 0));  // 방문 배열(이동 횟수 저장) 초기화
    queue<pair<int,int>> q;  // 큐 초기화

    q.push({start_x, start_y});  // 시작 위치 큐에 추가
    visited[start_x][start_y] = 0;  // 시작 위치 방문 처리

    while (!q.empty()) {
        auto [x,y] = q.front();  // 큐의 맨 앞 요소를 가져옴
        q.pop();  // 큐에서 제거

        if (x == target_x && y == target_y) {  // 목표에 도달한 경우
            cout << visited[x][y] << '\n';  // 이동 횟수 출력
            return;
        }

        for (int i = 0; i < 8; i++) {  // 모든 이동 방향에 대해
            int nx = x + dx[i];  // 새로운 x 좌표
            int ny = y + dy[i];  // 새로운 y 좌표

            // 이동할 수 있는지 확인
            if (nx >= 0 && nx < l && ny >= 0 && ny < l && visited[nx][ny] == 0) {
                visited[nx][ny] = visited[x][y] + 1;  // 이동 횟수 기록
                q.push({nx, ny});  // 큐에 추가
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> T;

    while (T--) {
        cin >> l;
        cin >> now_x >> now_y;
        cin >> target_x >> target_y;

        bfs(now_x, now_y);
    }

    return 0;
}

 

풀이

• 최단 거리를 찾는 문제 → BFS
• 이동할 수 있는 좌표라면 새로운 좌표까지의 이동 횟수를 현재 좌표까지의 이동 횟수 +1로 설정하고 방문처리
• 목표 좌표에 도달하면 해당 좌표까지의 이동 횟수를 리턴하고 종료한다