[알고리즘] 백준 14497

백준 14497번 주난의 난(難)

해결 과정 요약

bfs를 이용하여 풀 수 있다.
덱을 이용하여 1을 만나면 visited값을 올려주고 push_back 하고
0을 만나면 visited값을 올려주지 않고 push_front를 해줌으로써 파동을 구현할 수 있다.
범인을 만나면 리턴하고 범인의 위치의 visited -1 을 출력하면 된다.

풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

int N,M,sy,sx,ey,ex;
char m[304][304];
int visited[304][304];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
deque<pair<int,int>> q;

void bfs(){
    visited[sy][sx] = 1;
    q.push_back({sy, sx});
    while(q.size()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop_front();
        if(y == ey && x == ex) break;
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 1 || nx < 1 || ny > N || nx > M || visited[ny][nx]) continue;
            if(m[ny][nx] == '0'){
                visited[ny][nx] = visited[y][x];
                q.push_front({ny, nx});
            }
            else{
                visited[ny][nx] = visited[y][x] + 1;
                q.push_back({ny, nx});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> sy >> sx >> ey >> ex;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >> m[i][j];
        }
    }
    bfs();
    cout << visited[ey][ex] - 1 << "\n";
    return 0;
}

코멘트

쉬움