[백준] 16441번 아기돼지와 늑대 (C++)

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

 

 

이 문제는 N X M 격자그래프 배열이 주어지며 이때 초원, 빙판, 산, 늑대가 주어지며 이때 늑대가 움직일 수 있는 경로를 탐색해서

늑대가 못가는 경로에는 P를 출력하는 문제이다.

 

이때 빙판을 밟으면 이전에 빙판을 밟았던 방향으로 계속 이동하며 산이나 초원을 만날때까지 계속 움직여야 한다.

 

이후 부딪히고 난 이후 다른방향으로 이동할 수 있다.

 

따라서 모든 경로를 탐색하기 위해 bfs(너비 우선 탐색)을 사용하여 모든 갈 수 있는 경로를 방문체크하여 탐색하였다.

 

이때 빙판을 마주칠 경우 while 문을 사용하여 빙판을 마주치치않을때까지 반복하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
char graph[101][101];
queue<pii> q;
bool visited[101][101];

void bfs() {
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

            if(graph[nx][ny] == '.' && !visited[nx][ny]) {
                q.push({nx, ny});
                visited[nx][ny] = true;
            }
            else {
                while(graph[nx][ny] != '.') {
                    if(graph[nx][ny] == '#') {      // 벽인 경우
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                    nx += dx[i];
                    ny += dy[i];
                }
                if(!visited[nx][ny]) {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

void Print() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cout << visited[i][j] << " ";
        }
        cout << endl;
    }
}

void solve() {
    bfs();

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(graph[i][j] != '.') {
                cout << graph[i][j];
            }
            else {
                if(!visited[i][j]) {
                    cout << "P";
                }
                else cout << graph[i][j];
            }
        }
        cout << endl;
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];

            if(graph[i][j] == 'W') {
                q.push({i, j});
                visited[i][j] = true;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}