[백준/17129][C++] 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

문제

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

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

풀이

처음에는 모든 거리를 다 구한뒤, 3,4,5까지의 거리가 모두 -1인 경우만 NIE를 출력했고 이외의 경우에는 -1을 제외하고 최솟값을 구해주었다..

근데 어차피 BFS는 근처에 있는거 먼저가니까 BFS하는 와중에 3,4,5를 만나면 믿음을 가지고 chk 변수를 두어보았더니 성공했다. break문의 탈출은 아무래도 for문 탈출을 의미하나보다.... while문까지 탈출하려면 chk변수가 필요했다

코드

좀 더 효율적인 코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;
string board[3002];
int dist[3002][3002];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int n,m;
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    queue <pair<int,int>> q;

    for(int i=0;i<n;i++){
        cin>>board[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dist[i][j]=-1; //거리 초기화
            if(board[i][j] == '2'){ //보드 값이 2이면 식구를의미
                q.push({i,j}); //여기서부터 bfs시작해야함
                dist[i][j] = 0; //거리 0으로 만들어줌
            }

        }
    }
    int ans =-1;
    int chk=0;
    while(!q.empty()){
        //큐가 비어있지 않으면 bfs시작
        pair<int,int> cur = q.front();
        q.pop();
        for(int dir =0;dir<4;dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(board[nx][ny] == '1'||dist[nx][ny]!=-1) continue; 
            if(board[nx][ny] == '3'||board[nx][ny]=='4'||board[nx][ny]=='5'){
                 ans = dist[cur.first][cur.second] + 1;
                 chk = 1;
                 break; //더이상 진행할 필요 없음
             }
            q.push({nx,ny});
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
        }
        if(chk == 1) break;
    }
    if(ans == -1){
        cout<<"NIE";
        return 0;
    }

    cout<<"TAK\n"<<ans;

}

chk변수를 두지 않으면... 실행이 안된다. 이것때문에 계속 틀렸던 거였음..

#include <iostream>
#include <queue>
#include <string>
using namespace std;
string board[3002];
int dist[3002][3002];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int n,m;
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    queue <pair<int,int>> q;

    for(int i=0;i<n;i++){
        cin>>board[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dist[i][j]=-1; //거리 초기화
            if(board[i][j] == '2'){ //보드 값이 2이면 식구를의미
                q.push({i,j}); //여기서부터 bfs시작해야함
                dist[i][j] = 0; //거리 0으로 만들어줌
            }

        }
    }
    while(!q.empty()){
        //큐가 비어있지 않으면 bfs시작
        pair<int,int> cur = q.front();
        q.pop();
        for(int dir =0;dir<4;dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(board[nx][ny] == '1'||dist[nx][ny]!=-1) continue; 
            // if(board[nx][ny] == '3'||board[nx][ny]=='4'||board[nx][ny]=='5'){
            //     //만약에 음식을 찾았어?
            //     ans = dist[cur.first][cur.second] + 1;
            //     break; //더이상 진행할 필요 없음
            // }
            q.push({nx,ny});
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
        }
    }
    int ans[3];
    int p = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            //만약 보드가 3,4,5중 하나면?
            if(board[i][j]=='3'||board[i][j]=='4'||board[i][j]=='5'){
                ans[p] = dist[i][j];
                p++;
            }
        }
    }
    int cnt =0;
    int answer;
    for(auto a:ans){
        if(a==-1){
            cnt++;
        }
        else{
            answer = a;
        }
    }
    if(cnt==3){
        cout<<"NIE";
        return 0;
    }
    for(auto a:ans){
        if(a!=-1){
            answer = min(a,answer);
        }
    }
    cout<<"TAK\n"<<answer;

}

여덟번 찍어 안넘어 가는 나무가 있을뻔. 일일히 다 비교해서 작은게 뭔지.. 찾아냈다