백준 1600번 말이 되고픈 원숭이

문제 링크입니다: https://www.acmicpc.net/problem/1600

문제 자체는 쉽지만 코딩할 때 실수하기 딱 좋은 BFS(Breadth First Search) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 능력이 있을 경우에는 knight처럼 움직이고 해당 위치를 큐에 집어넣고, 능력이 없을 때처럼 움직이는 경우도 큐에 집어넣습니다.

-> 이 때, visited 함수를 좌표와 능력 사용 횟수를 이용해 표시하는 것이 핵심입니다! 즉, 같은 좌표라도 능력 사용 횟수가 다르면 visited 함수는 표시가 되어있지 않습니다.

2. 도착지점에 도달할 경우 움직인 횟수를 반환합니다.

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 200;

 

typedef struct

{

        int y, x;

}Dir;

 

//정상적인 상하좌우

Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };

//말의 움직임

Dir knightDir[8] = { { -1, -2 },{ -2, -1 },{ -2, 1 },{ -1, 2 },{ 2, 1 },{ 1, 2 },{ 2, -1 },{ 1, -2 } };

 

int K, W, H;

int board[MAX][MAX];

bool visited[MAX][MAX][30 + 2];

 

int BFS(int y, int x)

{

        queue < pair<pair<int, int>, pair<int, int>>> q; //y, x, K, cnt

        q.push(make_pair(make_pair(y, x), make_pair(0, 0)));

        visited[y][x][0] = 1;

 

        while (!q.empty())

        {

                 int curY = q.front().first.first;

                 int curX = q.front().first.second;

                 int knight = q.front().second.first;

                 int cnt = q.front().second.second;

                 q.pop();

 

                 if (curY == H - 1 && curX == W - 1)

                         return cnt;

 

                 //아직 능력을 쓸 수 있다면

                 if (knight < K)

                 {

                         for (int i = 0; i < 8; i++)

                         {

                                 int nextY = curY + knightDir[i].y;

                                 int nextX = curX + knightDir[i].x;

 

                                 if (0 <= nextY && nextY < H && 0 <= nextX && nextX < W)

                                          if (!visited[nextY][nextX][knight + 1] && !board[nextY][nextX])

                                          {

                                                  visited[nextY][nextX][knight + 1] = true;

                                                  q.push(make_pair(make_pair(nextY, nextX), make_pair(knight + 1, cnt + 1)));

                                          }

                         }

                 }

                 //능력 사용하지 않은 경우

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = curY + moveDir[i].y;

                         int nextX = curX + moveDir[i].x;

 

                         if (0 <= nextY && nextY < H && 0 <= nextX && nextX < W)

                                 if (!visited[nextY][nextX][knight] && !board[nextY][nextX])

                                 {

                                          visited[nextY][nextX][knight] = true;

                                          q.push(make_pair(make_pair(nextY, nextX), make_pair(knight, cnt + 1)));

                                 }

                 }

        }

        return -1;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상 위해

        cin >> K >> W >> H;

 

        for (int y = 0; y < H; y++)

                 for (int x = 0; x < W; x++)

                         cin >> board[y][x];

 

        cout << BFS(0, 0) << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~