Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 7562] 나이트의 이동 본문

대학교/Algorithm

[백준 7562] 나이트의 이동

SWKo 2020. 2. 27. 22:59

0. 제목

  • 백준 7562 나이트의 이동
  • BOJ 7562 나이트의 이동
  • C++ 7562 나이트의 이동

1. 문제

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


2. 풀이

  • dfs가 아닌 bfs를 이용한다.
  • bfs를 활용했을 때 목적지에 도착했을 당시 최소 이동 횟수이기 때문이다. dfs는 목적지에 도착했을 때 최소 이동 횟수가 아니기 때문이다.
  • 최소 이동 횟수를 구할 때는 bfs로 구해야 할 것같다.(내 생각)
  • 배열 arr은 출발지로부터 해당 좌표(i, j)까지의 최소 이동 횟수를 담아 놓은 것이다.
  • bfs방식으로 큐를 이용하여 출발 좌표부터 탐색을 시작하고 출발지 좌표가 나오면 그 때 arr배열의 값을 출력해주고 탈출하면 된다.
  • 테스트케이스도 입력을 받으니 테스트케이스를 하나 실행할때 마다 배열들을 초기화시켜준다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int arr[301][301];
bool checked[301][301];
 
int dx[8= {1,2,2,1,-1,-2,-2,-1};
int dy[8= {2,1,-1,-2,-2,-1,1,2};
 
int I;//체스판의 한 변의 길이
queue<pair<intint>> q;
int srcX, srcY, dstX, dstY;
 
void bfs(int a, int b){
    q.push(make_pair(a, b));
    checked[a][b] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == dstX && y == dstY){
            cout << arr[x][y] << '\n';
            
            while(!q.empty()){
                q.pop();
            }
            break;
        }
        
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < I && ny >= 0 && ny < I){
                if(checked[nx][ny] == false){
                    checked[nx][ny] = true;
                    arr[nx][ny] = arr[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int main(int argc, const char * argv[]) {
    int T;
    cin >> T;
 
    for(int i = 0; i < T; i++){
        cin >> I;
        cin >> srcX >> srcY >> dstX >> dstY;
        bfs(srcX, srcY);
        memset(arr, 0sizeof(arr));
        memset(checked, falsesizeof(checked));
    }
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1932] 정수 삼각형  (0) 2020.02.28
[백준 1735] 분수 합  (0) 2020.02.27
[백준 2252] 줄 세우기  (0) 2020.02.27
[백준 9935] 문자열 폭발  (0) 2020.02.26
[백준 1717] 집합의 표현  (0) 2020.02.26
Comments