(C++) - 백준(BOJ) 17129번 : 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

bfs문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

*정보섬의 정보를 char형으로 받아야 시간초과가 나지 않습니다. int형으로 받게 되면 시간초과가 납니다. 900만번의 scanf를 char형으로 받으셔야 합니다. 1. n ,m을 선언 후 입력받습니다. 2. board에 정보섬의 정보를 char형으로 입력받습니다. i행 j열에 2가 있다면 bfs의 시작좌표이므로 startR, startC에 i, j를 저장합니다.

 

📔 풀이과정

 bfs함수를 수행하면 됩니다. pop했을 때 '2'보다 크다면 음식이 있는 위치에 도달한 것이므로 그곳의 dist[r][c]를 반환합니다. 도착하지 못했다면 -1을 반환합니다.

 

 

📔 정답출력

bfs의 반환결과가 0이상이라면 TAK와 반환값을 출력합니다. -1이라면 도착하지 못했으므로 NIE를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using pii = pair <int,int>;
char board[3001][3001];
int n, m, dist[3001][3001], startR, startC;
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};

int bfs(){
    dist[startR][startC] = 0;
    queue <pii> q;
    q.push({startR, startC});
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        if(board[r][c] > '2') return dist[r][c];

        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
            if(board[nr][nc] == '1' || dist[nr][nc] >= 0) continue;

            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return -1;
}

int main(){
    fastio;
    cin >> n >> m;
    memset(dist, -1, sizeof(dist));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            if(board[i][j] == '2') startR = i, startC = j;
        }
    }
    int ans = bfs();
    if(ans == -1) cout << "NIE";
    else cout << "TAK\n" << ans;
}