http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30
문제 이해
현재 말의 위치에서 졸의 위치까지 최단 거리로 이동하는 문제이므로 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;
}
'컴퓨터기본 > 문제풀이' 카테고리의 다른 글
[백준] 1966번: 프린터 큐 (0) | 2021.09.14 |
---|---|
[정올] 1661 : 미로 탈출 로봇 (0) | 2021.09.14 |
[백준] 2589번: 보물섬 (0) | 2021.09.14 |
[백준] 15651번. N과 M(3) (0) | 2021.09.13 |
[백준] 15650번: N과 M (2) (0) | 2021.09.13 |