[백준 14497][C++] 주난의 난 - 문제풀이

해당 문제는 BFS를 적용하는데, 레벨링이 포함된 BFS라고 보면 된다. 

2가지 문제 풀이 방법이 있는데, 첫 번째는 Q를 2개 이용한 방법. 두 번째는 시뮬레이션 처럼 문제 그대로를 해석하여 푼 방법이다. 코드는 2번째 방법이 좀 더 직관적이다.

 

1. 

#include <stdio.h>
#include<algorithm>
#include<queue>
using namespace std; 
char a[301][301];
int n, m, x1, y1, x2, y2; 
typedef pair<int, int> pii;
int visited[301][301];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int ret; 
queue<int> q;
int main(){
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
    y1--, x1--, y2--, x2--; 
    for(int i = 0; i < n; i++){
        scanf("%s", a[i]); 
    }  
    q.push(1000 * y1 + x1);
    visited[y1][x1] = 1; 
    int cnt = 0; 
    while(a[y2][x2] != '0'){ 
        cnt++;
        queue<int> temp; 
        while(q.size()){
            int y = q.front() / 1000; 
            int x = q.front() % 1000;  
            q.pop();  
            for(int i = 0; i < 4; i++){
                int ny = y + dy[i]; 
                int nx = x + dx[i];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue; 
                visited[ny][nx] = cnt;  
                if(a[ny][nx] != '0'){
                    a[ny][nx] = '0'; 
                    temp.push(1000 * ny + nx);
                }
                else q.push(1000 * ny + nx); 
            }
        }
        q = temp;  
    }
    printf("%d\n", visited[y2][x2]); 
}

 

2. 

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <memory.h>
#include <math.h>

using namespace std;

int map[304][304];
int visited[304][304];
int n, m, x_1, y_1, x_2, y_2;

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

queue <pair<int, int>> q;

int cnt;

void erasePerson(void)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 2) map[i][j] = 0;
		}
	}
}

int findSuspect(void)
{
	int flag = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == ('#' - '0')) flag = 1;
		}
	}
	return flag;
}

void bfs(void)
{
	int y, x, ny, nx;

	q.push({ y_1,x_1 });
	visited[y_1][x_1] = 1;
	while (q.size())
	{

		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= m && visited[ny][nx] == 0)
			{
				if (map[ny][nx] == 1)
				{
					map[ny][nx] = 2;
					visited[ny][nx] = 1;
				}
				else if (map[ny][nx] == 0)
				{
					visited[ny][nx] = 1;
					q.push({ ny,nx });
				}
				else if (map[ny][nx] == ('#' - '0'))
				{
					cout << cnt;
					map[ny][nx] = 0;
					return;
				}
			}
		}
	}

}

int main()
{
	//freopen("input.txt", "rt", stdin);

	cin >> n >> m;
	cin >> y_1 >> x_1 >> y_2 >> x_2;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			map[i][j] = (int)(c - '0');
		}
	}

	while (findSuspect())
	{
		cnt++;
		bfs();
		erasePerson();
		memset(visited, 0, sizeof(visited));
	}

	return 0;
}