[백준 16441]아기돼지와 늑대

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

1)문제 분류

-시뮬레이션

2)문제 해결

- 방법 1) <BFS>늑대의 위치를 큐에 담아 돌릴때 늑대가 움직이는 방향까지 담아서 경로를 3차원으로 체크한다.

 -방법2)<DFS>늑대의 위치를 파악하고, 그 지점에서 재귀타고 2차원으로 체크 한다.

- 늑대가 한번이라도 왔던 곳이라면 safe[][]에 체크한다.

- 문제에서 잘 읽어야 할 부분이 ". 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다."  <-이거 못 읽어가지구 몇번 틀렸다 ㅎㅎ ..문제를 잘읽자.!

-safe[][]를 토대로 돼지가 집을 설치할수 있는 곳을 파악해서 출력한다.

<DFS>

#include<iostream>

#include<cstdio>

using namespace std;

int N, M;

char map[102][102];

int safe[102][102];// 한번이라도 늑대가 왔으면 안전한 지역이아님

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>N - 1 || ry>M - 1)return false;

else return true;

}

void DFS(int x, int y)

{

safe[x][y] = true; //안전지대아님을 체크

for (int i = 0; i < 4; i++)

{

int cx = x + xrr[i]; int cy = y + yrr[i];

if (range(cx, cy) == false || safe[cx][cy] == true || map[cx][cy] == '#')continue;

if (map[cx][cy] == 'W' || map[cx][cy] == '.') //초원일때

{

DFS(cx, cy);

}

else //빙판일때

{

while (range(cx, cy) && map[cx][cy] == '+')

{

cx += xrr[i];

cy += yrr[i];

}

if (map[cx][cy] == '#') //산에 부딪혔을때 빙판다른방향으로 이동

{

cx -= xrr[i];

cy -= yrr[i];

}

if (safe[cx][cy]==false) //초원이나, 산에부딪혔을때 다른방향이동

{

DFS(cx, cy);

}

}

}

}

int main()

{

cin >> N >> M;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

scanf(" %c",&map[i][j]);

}

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

if (map[i][j] == 'W')DFS(i, j);

}

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

if (safe[i][j] == false && map[i][j] == '.')

{

printf("P");

}

else

{

printf("%c",map[i][j]);

}

}

printf("\n");

}

}

<BFS>

#include<iostream>

#include<vector>

#include<queue>

#include<cstdio>

using namespace std;

int N, M;

char map[102][102];

int chk[102][102][5]; //늑대가 움직이는 경로 체크

int safe[102][102];// 한번이라도 늑대가 왔으면 안전한 지역이아님

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

typedef struct Data

{

int x, y, dir;

}Data;

vector<Data> wolf;

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>N - 1 || ry>M - 1)return false;

else return true;

}

void BFS(int x, int y, int dir)

{

queue<Data>pq;

pq.push({ x,y,dir });

safe[x][y] = true; //안전지대아님

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

safe[output.x][output.y] = true;//안전지대아님

Data input;

input.dir = output.dir;

input.x = output.x + xrr[input.dir];

input.y = output.y + yrr[input.dir];

if (range(input.x, input.y) && map[input.x][input.y] != '#'&&chk[input.x][input.y][input.dir]==false)

{

chk[input.x][input.y][input.dir] = true;

if (map[input.x][input.y] == '.')

{

for (int d = 0; d < 4; d++)

{

pq.push({ input.x,input.y,d });

}

}

else if (map[input.x][input.y] == '+')

{

int curx = input.x;

int cury = input.y;

while (range(curx, cury) && map[curx][cury] == '+')

{

curx += xrr[input.dir];

cury += yrr[input.dir];

}

if (range(curx, cury))

{

if (map[curx][cury] == '#')

{

curx -= xrr[input.dir];

cury -= yrr[input.dir];

}

for (int d = 0; d < 4; d++)

{

pq.push({ curx,cury,d });

}

}

}

}

}

}

int main()

{

cin >> N >> M;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

scanf(" %c", &map[i][j]);

if (map[i][j] == 'W')

{

wolf.push_back({ i,j });

map[i][j] == '.';

}

}

}

for (int i = 0; i < wolf.size(); i++)

{

for (int dir = 0; dir < 4; dir++)

BFS(wolf[i].x, wolf[i].y, dir); //방향

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

if (safe[i][j] == false && map[i][j] == '.')

{

printf("P");

}

else

{

printf("%c",map[i][j]);

}

}

printf("\n");

}

}