오늘의 학습 키워드

• 삼성 코테 빈출 유형: 시뮬레이션 + BFS
• 삼성 코딩 테스트 형식: 여러 테스트 케이스(TC)를 한 번에 처리하는 방식
• BFS를 활용한 최소 이동 횟수 계산

[백준] 나이트의 이동 - 7562

• [백준] 나이트의 이동 - 7562
• Silver I
• C++ 풀이
• 풀이시간: 11m

문제해설

이 문제는 체스의 나이트가 출발지에서 목적지까지 이동할 때 최소 이동 횟수를 구하는 문제이다.

접근법: BFS

나이트의 이동 좌표 설정

나이트의 이동 가능 좌표 dx, dy는 총 8가지로 설정할 수 있습니다. 나이트는 $(x_{new}, y_{new}) \rightarrow (x \pm 2, y \pm 1) \text{ or } (x \pm 1, y \pm 2)$의 조합으로 움직이기 때문에, 이를 반영하여 이동 좌표를 정의한다.

BFS로 최소 이동 수 구하기

출발지에서 목적지까지 이동할 때 최소 이동 횟수를 구하기 위해 BFS를 사용하여 거리 dist를 업데이트한다.

$distX_{new}, distY_{new}=distX, distY + 1$

여러 개의 테스트 케이스로 구성된 문제 (삼성 기출 형식과 유사)

방문 여부를 저장하는 배열 board[x][y]는 매 테스트 케이스마다 새로 초기화해야 한다. 삼성 코딩 테스트와 같은 문제에서는 테스트 케이스별로 초기화가 중요한데, C++에서는 memset 함수를 통해 간단하게 초기화할 수 있다.

#define X first
#define Y second
#include <bits/stdc++.h>
using namespace std;

int N, l;
int board[302][302];
pair<int, int> start, target;

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

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

    cin >> N;

    while(N--){
        memset(board, 0, sizeof(board));
        cin >> l;
        int x, y;
        cin >> x >> y;
        start = {x, y};
        cin >> x >> y;
        target = {x, y};

        queue<pair<int, int>> Q;
        Q.push(start);
        board[start.X][start.Y] = 1;

        while(!Q.empty()){
            auto cur = Q.front(); Q.pop();
            if (cur == target) break;
            for (int i = 0; i < 8; i++){
                int nx = cur.X + dx[i], ny = cur.Y + dy[i];
                if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
                if (board[nx][ny] > 0) continue;
                Q.push({nx, ny});
                board[nx][ny] = board[cur.X][cur.Y] + 1;
            }
        }
        cout << board[target.X][target.Y] - 1 << "\n";
    }

}

오늘의 회고

오늘의 문제는 삼성 코딩 테스트 유형과 형식을 연습하기에 좋은 문제이다. 최근 SW 역량 테스트 준비를 통해 익숙해진 덕분에 11분 만에 문제를 풀 수 있었다.

• 유형: 삼성 문제는 보통 시뮬레이션 문제 + BFS 유형을 조합한 형식으로 나오는 경우가 많아, 워밍업으로 좋은 문제인 것 같다.
• 형식: 여러 테스트 케이스를 한 번에 처리하는 형식은 삼성 코딩 테스트에서 쓰는 방식이다. memset 함수를 쓰면 간편하게 초기화할 수 있으니 쓰는 것을 추천한다.