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
관리 메뉴

풀이 보관함

[C++] 백준 7562번 : 나이트의 이동 본문

problem solving/백준

[C++] 백준 7562번 : 나이트의 이동

viin 2022. 8. 4. 21:47

문제

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

풀이

 

방문한 순서대로 좌표를 저장하기 위한 데이터 타입으로 pair를 가지는 queue를 선언했다.

std::queue<std::pair<int, int>> q;

 

 

🔍 knight()

 

  • 처음 함수를 실행하면 (0, 0)에서 방문할 수 있는 위치들를 탐색하여 목표 지점에 왔는지 확인한다.
  • 첫번째 이동으로 갈 수 있는 모든 위치를 queue에 저장한다.
    • 이 때, 재방문 방지를 위해 min[x][y] == 0 이라는 조건을 달아주었다. (한번도 방문 안한 곳이라면 queue에 넣는다.)
  • queue에는 다음 이동으로 갈 수 있는 모든 위치를 갖게 된다.

이 과정을 (N, M)까지 반복한다. (N, M)에 도달하면 바로 return 하기 때문에 최소 이동 횟수을 바로 알 수 있다. (BFS 특성)

  • 채점 데이터는 무조건 (N, M)에 갈 수 있도록 주어졌지만 혹시나해서 while(!q.empty())라는 조건을 달아주었다.

 

 

🚩주의할 점

 

#include <memory.h>

// ..

memset(min, 0, sizeof(min));

라이브러리 추가 잊지 않기

 

 

 

bool isValidRange(int a, int b)
{
    if(a <l && b <l && a >= 0 && b >= 0)
        return true;

    return false;
}

체스판 이동을 해줄 때 반드시 범위 체크를 해주어야 한다.

a <= l가 아니라 a < l 이라는 점을 유의.

 

소스

#include <iostream>
#include <memory.h> // memset
#include <queue>
#define MAX 302
 
int min[MAX][MAX];
int X, Y = 0// 현재 좌표
int N, M = 0// 목표 좌표
int l = 0;
 
bool isValidRange(int a, int b)
{
    if(a <&& b <&& a >= 0 && b >= 0)
        return true;
    
    return false;
}
 
void knight(int _x, int _y)
{
    //BFS
    std::queue<std::pair<intint>> q;
    q.push(std::make_pair(_x, _y));
    
    int xPos[8= {21-1-2-2-112};
    int yPos[8= {-1-2-2-11221};
 
    while(!q.empty())
    {
        int nowX = q.front().first;
        int nowY = q.front().second;
        
        if(nowX == N && nowY == M) return;
 
        q.pop();
 
        
        for(int i=0; i<8++i)
        {
            int x = nowX + xPos[i];
            int y = nowY + yPos[i];
            
            if(!isValidRange(x, y))  continue;
            
            if(min[x][y] == 0 || min[x][y] > min[nowX][nowY]+ 1)
            {
                min[x][y] = min[nowX][nowY] + 1;
                q.push(std::make_pair(x, y));
            }
            
        }
    }
    
}
 
int main()
{
    int T = 0std:: cin >> T;
    while(T--)
    {
        std::cin >> l >> X >> Y >> N >> M;
        memset(min, 0sizeof(min));
        knight(X, Y);
        std::cout << min[N][M] << "\n";
    }
    
    return 0;
}
cs

 

 


 

+ tmi

더보기


DFS로 풀었다가 시간 초과를 봤습니다. 왜 DFS로는 안될까 검색을 하다가 아래 글을 봤습니다. 

그래서 BFS로 풀었습니다.

 

'최소'라는 용어가 나오면
BFS로 풀어야합니다.
​
마찬가지로 미로찾기 같이 '최소'의 수로 빠져나와야 한다던지
그런 느낌의 문제는 전부 BFS로 접근하시면 됩니다.


[출처] [자바] 백준 7562 : 나이트의 이동 (BFS 문제 풀어보기)|작성자 sosow0212

 

 

#include <iostream>
#include <memory.h> // memset
#define MAX 302
 
int min[MAX][MAX];
int X, Y =0// 현재 좌표
int N, M = 0// 목표 좌표
int l =0;
 
bool isValidRange(int a, int b)
{
    if(a <=&& b <=&& a >= 0 && b >= 0)
        return true;
    
    return false;
}
 
void knight(int x, int y)
{
    if(x == N && y == M)
    {
        return;
    }
    
    int xPos[8= {21-1-2-2-112};
    int yPos[8= {-1-2-2-11221};
    
    for(int i=0; i<8++i)
    {
        // x, y는 현재 좌표
        // r, c는 이동 가능한 좌표
        int r = x + xPos[i];
        int c = y + yPos[i];
        
        //std::cout << "[TEST] r: " << r << "\tc: " << c << std::endl;
        
        if(!isValidRange(r, c)) continue;
        
        if(min[r][c] == -1 || min[r][c] > min[x][y]+ 1)
        {
            min[r][c] = min[x][y] + 1;
            knight(r, c);
        }
    }
    
}
 
int main()
{
    int T = 0std:: cin >> T;
    while(T--)
    {
        std::cin >> l >> X >> Y >> N >> M;
        memset(min, -1sizeof(min));
        knight(X, Y);
        std::cout << min[N][M] + 1 << "\n";
    }
    
    return 0;
}
 
cs

 

반응형
Comments