[Baekjoon]백준 7562 나이트의 이동(실버 1) - Python/C/C++

문제설명

문제를 살펴보면 이번에는 한 칸씩만 이동한 것과 다르게 체스의 말로 움직이기 때문에 

조금 어렵게 느껴질 수는 있으나 dx, dy 배열에서 말이 움직일 수 있는 위치만큼 지정해주면 이전 문제와 동일하다

이전에는 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]과 같이 지정해주었다면

이번에는 dx = [-2, -2, -1, -1, 1, 1, 2, 2], dy = [1, -1, 2, -2, 2, -2, 1, -1]와 같이 지정해주면된다

또한, 이번에도 행과 열로 계산이 이루어지기 때문에 x, y와 같은 index 계산에 헷갈리지 않도록 유의해야한다

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(x, y):
    queue = deque([(x, y)])
    chess[y][x] = 0
    while queue:
        x, y = queue.popleft()
        if x == target_x and y == target_y:
            return chess[y][x]
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < size and 0 <= ny < size and chess[ny][nx] == 0:
                chess[ny][nx] = chess[y][x] + 1
                queue.append((nx, ny))
        
                
case = int(input())
for _ in range(case):
    size = int(input())
    chess = [[0 for _ in range(size)] for _ in range(size)]
    now_x, now_y = map(int, input().split())
    target_x, target_y = map(int, input().split())
    print(bfs(now_x, now_y))

#include <stdio.h>

#define MAX 300

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

int chess[MAX][MAX];
int qx[MAX * MAX];
int qy[MAX * MAX];
int front, rear;
int size, target_x, target_y;

int bfs(int sx, int sy) {
    front = rear = 0;
    qx[rear] = sx;
    qy[rear] = sy;
    rear++;
    chess[sy][sx] = 0;

    while (front < rear) {
        int x = qx[front];
        int y = qy[front];
        front++;

        if (x == target_x && y == target_y) {
            return chess[y][x];
        }

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < size && ny >= 0 && ny < size && chess[ny][nx] == -1) {
                chess[ny][nx] = chess[y][x] + 1;
                qx[rear] = nx;
                qy[rear] = ny;
                rear++;
            }
        }
    }
    return -1;
}

int main() {
    int Case;
    scanf("%d", &Case);

    while(Case--) {
        int n;
        scanf("%d", &n);
        size = n;

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                chess[i][j] = -1;
            }
        }

        int now_x, now_y;
        scanf("%d %d", &now_x, &now_y);
        scanf("%d %d", &target_x, &target_y);

        printf("%d\n", bfs(now_x, now_y));
    }

    return 0;
}

 

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

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

int bfs(int size, int now_x, int now_y, int target_x, int target_y) {
    vector<vector<int>> chess(size, vector<int>(size, 0));
    queue<pair<int, int>> q;

    q.push({now_x, now_y});
    chess[now_y][now_x] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == target_x && y == target_y)
            return chess[y][x];

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < size && ny >= 0 && ny < size && chess[ny][nx] == 0) {
                chess[ny][nx] = chess[y][x] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int size, now_x, now_y, target_x, target_y;
        cin >> size;
        cin >> now_x >> now_y;
        cin >> target_x >> target_y;

        cout << bfs(size, now_x, now_y, target_x, target_y) << "\n";
    }

    return 0;
}

C언어의 경우 2차원 배열을 만드는 것이 아니라 1차원 배열 2개로 해결하였다

직관적으로 해결가능함과 동시에 C++처럼 queue<pair<int,int>> 같은 STL을 사용할 수 없기 때문이다

변환 과정에서 실수가 일부 있었지만, 다음부터는 파이썬 코드 자체도 참고하지 않고 처음부터 작성하는 연습을 해보아야겠다