[BaekJoon 25416번] 빠른 숫자 탐색(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

25416번: 빠른 숫자 탐색

 

 

[문제 설명]

 

 

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1중 하나의 숫자가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽 방향으로 1씩 증가한다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다. -1이 적혀 있는 칸으로는 이동할 수 없고 0, 1이 적혀 있는 칸으로는 이동할 수 있다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한 방향으로 한 칸 이동할 수 있다. 학생이 현재 위치 (r, c)에서 시작하여 1이 적혀 있는 칸에 도착하기 위한 최소 이동 횟수를 출력하자. 현재 위치 (r, c)에서 시작하여 1이 적혀 있는 칸으로 이동할 수 없는 경우 –1을 출력한다. 보드에는 1이 적혀 있는 격자가 1개 주어진다.

 

 

[입력]

 

 

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 정보가 순서대로 주어진다. i번째 줄의 j번째 숫자는 보드의 (i - 1)번째 행, (j - 1)번째 열의 정보를 나타낸다. 보드의 정보는 -1, 0, 1중 하나이다.

다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.

 

 

[출력]

 

 

학생이 현재 위치 (r, c)에서 1이 적혀 있는 칸에 도착하기 위한 최소 이동 횟수를 출력한다. 현재 위치 (r, c)에서 1이 적혀 있는 칸으로 이동할 수 없는 경우 -1을 출력한다.

 

 

[제한]

 

 

0 ≤ r, c ≤ 4
학생의 현재 위치 (r, c)에는 0이 적혀 있다.
1이 적혀 있는 격자가 1개 주어진다.

 

 

[입출력 예]

 

 

입력	출력
0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 1 1	2
0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 1 1 1	-1

 

 

[문제 풀이]

 

 

BFS 문제이다.

보드의 정보를 입력받을 때 이동 횟수를 저장할 배열(dis)을 -1로 초기화, 내가 도착할 1의 위치를 저장한다.

그리고 BFS 알고리즘을 사용하여 탐색한다.

 

void bfs() {
    queue<pair<int, int>> q;
    q.push({r, c});
    dis[r][c] = 0;
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            /* 조건 */
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            if((board[nx][ny] == -1) ||  (dis[nx][ny] > -1)) continue;
            
            q.push({nx, ny});
            dis[nx][ny] = dis[cur.first][cur.second] + 1;
        }
    }
}

 

if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
if((board[nx][ny] == -1) ||  (dis[nx][ny] > -1)) continue;

위 코드와 같이

다음 위치를 찾을 때 범위에 맞지않은 지점과

다음 위치가 -1인 경우 그리고 이동 횟수를 저장할 배열(dis)이 -1보다 크다면 이미 방문했던 지점이기 때문에 패스하는 조건을 걸어줘야한다.

 

위 조건을 지나오면 큐에 다음 위치 좌표를 넣고,

이동 횟수를 저장할 배열(dis)의 다음 위치 = 이동 횟수를 저장할 배열(dis)의 현재 위치 + 1을 함으로서 이동 횟수를 구할 수 있다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[5][5];
int dis[5][5];
int r, c; // 학생의 위치

void bfs() {
    queue<pair<int, int>> q;
    q.push({r, c});
    dis[r][c] = 0;
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            if((board[nx][ny] == -1) ||  (dis[nx][ny] > -1)) continue;
            q.push({nx, ny});
            dis[nx][ny] = dis[cur.first][cur.second] + 1;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int oneX, oneY;
    for(int i = 0; i < 5; ++i) {
        fill(dis[i], dis[i] + 5, -1);
        for(int j = 0; j < 5; ++j) {
            cin >> board[i][j];
            if(board[i][j] == 1) {
                // 1의 위치
                oneX = i;
                oneY = j;
            }
        }
    }
    cin >> r >> c;
    bfs();
    cout << dis[oneX][oneY];
    return 0;
}