[백준 14497][C++] 주난이의 난(難)

문제 링크

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

14497번: 주난의 난(難)

 

---

◆문제 해결 및 설명◆

문제 해설 : 생략

말이 좀 어려워서 애를 먹었는데(잘못된거 같기도) 예제를 보면 주난이와 이어진 0들의의 상하좌우를 0으로 만들어준다.

입력 예제 1번을 그림을 통해 표현해 보았다. 3번뛰면 (0,1)이 지워지면서 정답임을 알 수 있다.

일단, 교실의 정보를 저장할 변수 mapS과 위치정보(y10, x1, y2, x2)를 저장하고, 교실의 입력이 문자열로 되어있어 이를 int형식 map으로 변환해주었다. 주난이와 도둑은 0과 1로 변환했다.

int main()
{
    cin >> n >> m;
    cin >> y10 >> x1 >> y2 >> x2;
    y10--, x1--, y2--, x2--;

    mapS = vector<string>(n);
    map = vector<vector<int>>(n, vector<int>(m));
    cin.ignore();
    for (int i = 0; i < n; i++)
    {
        getline(cin, mapS[i]);
    }
    mapS[y10][x1] = '0';
    mapS[y2][x2] = '1';

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            map[i][j] = mapS[i][j] - '0';
        }
    }
	...

 

이 문제를 풀기위해 주난이가 뛸때마다. 다익스트라를 사용하였다.

1e8으로 초기화된 거리를 저장할 distanceMap을 만들어서, 상하좌우로 갔을때, 주난이가 갈 수 있는 최단거리를 구하였다.

도둑이 0으로 바뀌었을때 주난이가 뛴 횟수를 출력하고 프로그램을 종료시켰다.

    int cnt = 0;
    while (1)
    {
        // Initialize variables
        distanceMap = vector<vector<int>>(n, vector<int>(m, 1e8));
        
        cnt++;
        dijkstra(0, y10, x1);
        if (map[y2][x2] == 0)
        {
            cout << cnt;
            return 0;
        }
    }

이차원 배열 맵의 특수성을 감안하여, 우선순위 큐를 이용하여 다익스트라를 구현하였다. 

if (distance + map[ny][nx] < distanceMap[ny][nx]) 라면  distanceMap[ny][nx]을 갱신하고 que에 저장을 해주었다.

void dijkstra(int dist, int row, int col)
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> que;
    que.push({dist, row, col});

    while (!que.empty())
    {
        int distance;
        tie(distance, row, col) = que.top();
        que.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = row + dxy[i];
            int nx = col + dxy[3 - i];

            if (ny < 0 || ny >= n || nx < 0 || nx >= m)
            {
                continue;
            }
            if (distance + map[ny][nx] < distanceMap[ny][nx])
            {
                distanceMap[ny][nx] = distance + map[ny][nx];
                que.push({distanceMap[ny][nx], ny, nx});
            }
        }
    }

 

이후 distanceMap에 저장된 최단거리가 1이하라면 주난이의 파동이 닫는 위치임으로 해당 위치의 map을 0으로 바꿔 주었다.

	...
	// change map
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (distanceMap[i][j] <= 1)
            {
                map[i][j] = 0;
            }
        }
    }
    
    return;
}

 

이를 반복하면 몇번만에 끝낼 수 있었는지 확인할 수 있다.

◆코드 전문◆

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, x1, y10, x2, y2;
vector<string> mapS;
vector<vector<int>> map;
vector<vector<int>> distanceMap;
int dxy[]{1, -1, 0, 0};

void dijkstra(int dist, int row, int col)
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> que;
    que.push({dist, row, col});

    while (!que.empty())
    {
        int distance;
        tie(distance, row, col) = que.top();
        que.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = row + dxy[i];
            int nx = col + dxy[3 - i];

            if (ny < 0 || ny >= n || nx < 0 || nx >= m)
            {
                continue;
            }
            if (distance + map[ny][nx] < distanceMap[ny][nx])
            {
                distanceMap[ny][nx] = distance + map[ny][nx];
                que.push({distanceMap[ny][nx], ny, nx});
            }
        }
    }

    // change map
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (distanceMap[i][j] <= 1)
            {
                map[i][j] = 0;
            }
        }
    }

    return;
}

int main()
{
    cin >> n >> m;
    cin >> y10 >> x1 >> y2 >> x2;
    y10--, x1--, y2--, x2--;

    mapS = vector<string>(n);
    map = vector<vector<int>>(n, vector<int>(m));
    cin.ignore();
    for (int i = 0; i < n; i++)
    {
        getline(cin, mapS[i]);
    }
    mapS[y10][x1] = '0';
    mapS[y2][x2] = '1';

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            map[i][j] = mapS[i][j] - '0';
        }
    }

    int cnt = 0;
    while (1)
    {
        // Initialize variables
        distanceMap = vector<vector<int>>(n, vector<int>(m, 1e8));

        cnt++;
        dijkstra(0, y10, x1);
        if (map[y2][x2] == 0)
        {
            cout << cnt;
            return 0;
        }
    }
}