[정올] 1106 : 장기

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30 

JUNGOL

문제 이해

현재 말의 위치에서 졸의 위치까지 최단 거리로 이동하는 문제이므로 BFS를 사용하면 된다.

모든 경우를 탐색하는 경우가 아니라, 졸의 위치에 도착하면 BFS를 끝내면 된다. 

 

시간복잡도: 현재 위치에서 BFS를 수행하므로 약 100*100 (가로세로 최대길이)만큼을 반복할 것이다. 

 

작성 코드(C)

#include <stdio.h>

int N, M; // 행, 열
int R, C; // 말이 있는 행, 열
int S, K; // 졸이 있는 행, 열
int visited[100 + 10][100 + 10];

// 방향 벡터
int dy[] = { -2, -2, 1, -1, 2, 2, 1, -1};
int dx[] = { -1, 1, 2, 2, 1, -1, -2, -2};

// 큐
typedef struct pos {
    int y;
    int x; 
    int time;
}POS;

POS q[100 * 100 + 10];
int rp, wp;

void enq(int y, int x, int time) {
    q[wp].y = y;
    q[wp].x = x;
    q[wp].time = time;
    wp++;
}

POS deq(void) {
    POS tmp = q[rp];
    rp++;
    return tmp;
}

int empty() {
    return wp == rp;
}

int BFS(int y, int x, int time) {

    enq(y, x, time);
    visited[y][x] = 1;

    while (!empty()) {
        POS cur = deq();

        if (cur.x == K && cur.y == S) return cur.time;

        for (int i = 0; i < 8; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if (ny < 1 || ny > N) continue;
            if (nx < 1 || nx > M) continue;
            if (visited[ny][nx] != 0) continue;

            enq(ny, nx, cur.time + 1);
            visited[ny][nx] = cur.time+1;
        }
    }

    return 0;
}

int main(void) {
       
    int ans;
    //get inputs
    scanf("%d %d", &N, &M);
    scanf("%d %d", &R, &C);
    scanf("%d %d", &S, &K);

    ans = BFS(R, C, 0);

    printf("%d", ans);
    return 0;
}

작성 코드2(C++)

#include <iostream>
#include <queue>

using namespace std;

int N, M; // 행, 열
int R, C; // 말이 있는 행, 열
int S, K; // 졸이 있는 행, 열
int visited[100 + 10][100 + 10];

// 방향 벡터
int dy[] = { -2, -2, 1, -1, 2, 2, 1, -1};
int dx[] = { -1, 1, 2, 2, 1, -1, -2, -2};

// 큐
typedef struct pos {
    int y;
    int x; 
    int time;
}POS;

queue<POS> q;

int BFS(int y, int x, int time) {

    POS tmp = {y, x, time};
    q.push(tmp);
    visited[y][x] = 1;

    while (!q.empty()) {
        POS cur = q.front();
        q.pop();

        if (cur.x == K && cur.y == S) return cur.time;

        for (int i = 0; i < 8; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if (ny < 1 || ny > N) continue;
            if (nx < 1 || nx > M) continue;
            if (visited[ny][nx] != 0) continue;

            POS tmp2 = {ny, nx, cur.time+1};
            q.push(tmp2);
            visited[ny][nx] = cur.time+1;
        }
    }

    return 0;
}

int main(void) {
       
    int ans;
    //get inputs
    cin >> N >> M;
    cin >> R >> C;
    cin >> S >> K;

    ans = BFS(R, C, 0);

    cout << ans;
    return 0;
}