백준 2391 - 가스관

 

 

문제 설명

러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.

이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.

블록 '|'	블록 '-'	블록 '+'	블록 '1'	블록 '2'	블록 '3'	블록 '4'

가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.

파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.

해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 이미 설계된 파이프 중 하나가 빠져있다.

빠진 위치와 파이프의 유형을 구하는 것이다.

 

이 문제를 풀기 위해서는 두 가지 작업이 필요하다.

• 파이프가 빠진 위치를 찾는다.
• 빠진 파이프의 유형을 찾는다.

우선, 첫 번째 작업을 보자.

파이프는 완전하게 설계되어 있다.

즉, 파이프를 시작부터 따라가면 반드시 끝부분에 도착해야 한다.

만약, 하나가 빠졌다면 파이프를 따라가다 빈칸을 마주하게 될 것이다.

그렇다면 해당 부분이 바로 빠진 위치가 된다.

 

파이프를 따라가기 위해서는 시작 위치에서부터 하나하나 살펴보면 된다.

'M'에서 4방향을 살펴 본 뒤 움직일 수 있는 위치가 단 한 군데일 것이다.

파이프는 완전하게 설계되어 있기 때문이다.

그렇다면 시작 방향을 설정할 수 있다.

int dir = -1;

for (int i = 0; i < 4; i++)
{
    int newY = pos.first + dy[i];
    int newX = pos.second + dx[i];

    if (newY <= 0 || newY > N || newX <= 0 || newX > M) continue;
    if (Gas[newY][newX] == '.') continue;

    for (int j = 0; j < 4; j++)
    {
        if (Possible[i][j] == Gas[newY][newX])
        {
            dir = i;
            break;
        }
    }
}

 Possible은 이동하려는 방향에 올 수 있는 파이프의 유형을 미리 계산한 것이다.

해당 방향으로 파이프가 뚫려있으면 된다.

Possible[0].push_back('|');
Possible[0].push_back('+');
Possible[0].push_back('1');
Possible[0].push_back('4');

Possible[1].push_back('-');
Possible[1].push_back('+');
Possible[1].push_back('3');
Possible[1].push_back('4');

Possible[2].push_back('|');
Possible[2].push_back('+');
Possible[2].push_back('2');
Possible[2].push_back('3');

Possible[3].push_back('-');
Possible[3].push_back('+');
Possible[3].push_back('1');
Possible[3].push_back('2');

 

그럼 이제 시작 방향을 잡았으니 하나하나 따라가 보자.

'-', '|', '+'는 이동하는 방향을 변경하지 않지만, '1', '2', '3', '4'는 방향을 변경시킨다.

그러니 이동하려는 칸의 파이프 유형을 살펴본 후, 방향을 변경시키며 이동하면 된다.

int ChangeDir(char pipe, int dir)
{
    if (pipe == '1')
    {
        if (dir == 0) dir = 1;
        if (dir == 3) dir = 2;
    }
    else if (pipe == '2')
    {
        if (dir == 2) dir = 1;
        if (dir == 3) dir = 0;
    }
    else if (pipe == '3')
    {
        if (dir == 1) dir = 0;
        if (dir == 2) dir = 3;
    }
    else if (pipe == '4')
    {
        if (dir == 1) dir = 2;
        if (dir == 0) dir = 3;
    }

    return dir;
}

while (true)
{
    int newY = pos.first;
    int newX = pos.second;
    newY += dy[dir];
    newX += dx[dir];

    dir = ChangeDir(Gas[newY][newX], dir);
    pos = { newY, newX };
}

만약, 이동하는 과정에서 빈칸('.')을 만난다면 해당 위치가 파이프가 빠진 위치가 된다.

따라서, 두 번째 작업을 수행하면 된다.

 

두 번째 작업은 빈 칸의 파이프에 어떠한 파이프가 들어갈지 확인하는 과정이다.

이 작업은 원래 7가지의 파이프를 모두 살펴봐야 하지만 잘 생각해 보면 4가지로 줄일 수 있다.

파이프를 따라가는 과정에서 빠진 칸에 들어가는 방향이 결정된다. 

즉, 방향이 정해져 있으니 빠진 칸에 올 수 있는 파이프는 최대 4개가 된다.

그럼 이제 문제는 간단하다.

빠진 칸에 가능한 4가지의 파이프를 하나씩 넣어보고 도착지까지 잘 수 있는지 확인하면 된다.

bool Simulate(vector<vector<char>>& Gas, pair<int,int> pos, pair<int,int>& end, int dir)
{
    bool bResult = false;
    while (true)
    {
        int& newY = pos.first;
        int& newX = pos.second;
        newY += dy[dir];
        newX += dx[dir];

        if (newY <= 0 || newY > N || newX <= 0 || newX > M) break;
        if (newY == end.first && newX == end.second)
        {
            bResult = true;
            break;
        }

        if (Gas[newY][newX] == '.') break;

        bool bPossible = false;
        for (int j = 0; j < 4; j++)
        {
            if (Possible[dir][j] == Gas[newY][newX])
            {
                bPossible = true;
                break;
            }
        }

        if (!bPossible) break;
        dir = ChangeDir(Gas[newY][newX], dir);
    }

    return bResult;
}


...

if (Gas[newY][newX] == '.')
{
    for (int i = 0; i < 4; i++)
    {
        Gas[newY][newX] = Possible[dir][i];
        if (Simulate(Gas, pos, end, dir))
        {
            cout << newY << " " << newX << " " << Possible[dir][i];
            return 0;
        }
    }

    break;
}

만약, 성공하는 경우가 생긴다면 해당 위치와 파이프의 유형을 출력하고 종료하면 된다.

그러지 못한 경우는 문제에서 없다고 보장했으니 신경 쓰지 않아도 된다. 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };
vector<vector<char>> Possible(4);

int ChangeDir(char pipe, int dir)
{
    if (pipe == '1')
    {
        if (dir == 0) dir = 1;
        if (dir == 3) dir = 2;
    }
    else if (pipe == '2')
    {
        if (dir == 2) dir = 1;
        if (dir == 3) dir = 0;
    }
    else if (pipe == '3')
    {
        if (dir == 1) dir = 0;
        if (dir == 2) dir = 3;
    }
    else if (pipe == '4')
    {
        if (dir == 1) dir = 2;
        if (dir == 0) dir = 3;
    }

    return dir;
}

bool Simulate(vector<vector<char>>& Gas, pair<int,int> pos, pair<int,int>& end, int dir)
{
    bool bResult = false;
    while (true)
    {
        int& newY = pos.first;
        int& newX = pos.second;
        newY += dy[dir];
        newX += dx[dir];

        if (newY <= 0 || newY > N || newX <= 0 || newX > M) break;
        if (newY == end.first && newX == end.second)
        {
            bResult = true;
            break;
        }

        if (Gas[newY][newX] == '.') break;

        bool bPossible = false;
        for (int j = 0; j < 4; j++)
        {
            if (Possible[dir][j] == Gas[newY][newX])
            {
                bPossible = true;
                break;
            }
        }

        if (!bPossible) break;
        dir = ChangeDir(Gas[newY][newX], dir);
    }

    return bResult;
}


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

    cin >> N >> M;
    vector<vector<char>> Gas(N+1, vector<char>(M+1));
    pair<int, int> pos;
    pair<int, int> end;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Gas[i][j];
            if (Gas[i][j] == 'M') pos = { i,j };
            if (Gas[i][j] == 'Z') end = { i,j };
        }
    }

    Possible[0].push_back('|');
    Possible[0].push_back('+');
    Possible[0].push_back('1');
    Possible[0].push_back('4');

    Possible[1].push_back('-');
    Possible[1].push_back('+');
    Possible[1].push_back('3');
    Possible[1].push_back('4');

    Possible[2].push_back('|');
    Possible[2].push_back('+');
    Possible[2].push_back('2');
    Possible[2].push_back('3');

    Possible[3].push_back('-');
    Possible[3].push_back('+');
    Possible[3].push_back('1');
    Possible[3].push_back('2');

    int dir = -1;

    for (int i = 0; i < 4; i++)
    {
        int newY = pos.first + dy[i];
        int newX = pos.second + dx[i];

        if (newY <= 0 || newY > N || newX <= 0 || newX > M) continue;
        if (Gas[newY][newX] == '.') continue;

        for (int j = 0; j < 4; j++)
        {
            if (Possible[i][j] == Gas[newY][newX])
            {
                dir = i;
                break;
            }
        }
    }

    while (true)
    {
        int newY = pos.first;
        int newX = pos.second;
        newY += dy[dir];
        newX += dx[dir];

        if (Gas[newY][newX] == '.')
        {
            for (int i = 0; i < 4; i++)
            {
                Gas[newY][newX] = Possible[dir][i];
                if (Simulate(Gas, pos, end, dir))
                {
                    cout << newY << " " << newX << " " << Possible[dir][i];
                    return 0;
                }
            }

            break;
        }

        dir = ChangeDir(Gas[newY][newX], dir);
        pos = { newY, newX };
    }

    return 0;
}

---