BOJ 백준 2931 가스관 < DFS>

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

 

< 가스관 >

 

1. 방향 지정

 

    UP : 0 , DOWN : 1, LEFT : 2, RIGHT : 3 로 가정

 

    방향이 전환되는 블록은 '1', '2', '3', '4' 의 경우이다.

    '1' 블록의 경우     UP(0)의 방향을 RIGHT(3)로, LEFT(2)의 방향을 DOWN(1)로 전환

    '2' 블록의 경우     DOWN(1)의 방향을 RIGHT(3)로, LEFT(2)의 방향을 UP(0)으로 전환

    '3' 블록의 경우     DOWN(1)의 방향을 LEFT(2)로, RIGHT(3)의 방향을 UP로 전환

    '4' 블록의 경우     UP(0)의 방향을 LEFT(2)로, RIGHT(3)의 방향을 DOWN(1)로 전환

 

    따라서,
    '1' 블록의 경우       방향 = (본래 방향 + 3) % 4

    '2', '4' 블록의 경우   방향 = (본래 방향 + 2) % 4

    '3' 블록의 경우       방향 = (본래 방향 + 1) % 4

    

    위와같이 방향을 전환시켜줄 수 있습니다.

 

2. 블록을 따라 이동하기 (DFS)

 

    고려해야할 점 )

 

    1. 블록은 한 개만 지을 수 있고, 그 한 블록을 짓게 되면 Z까지 도달할 수 있어야 한다.

    2. 블록을 짓고 블록을 따라 이동할 때, 다음 도착지가 내 방향으로 들어갈 수 있는 지 확인한다.

            쉽게 말해, 내 방향이 위로 올라가는 중인데 '-', '2', '3' 과 같은 블록이 다음 도착지라면

            막혀있는 것으로 판정해야 합니다.

    3. 필요없는 블록은 없다고 했으므로, 모든 블록을 돌아주어야 한다.

 

            

         위의 예시에서 가운데 블록인 '+'블록이 빠져 있는 문제라고 했을 때, 이 문제의 답은

         2 3 + 가 되어야 모든 블록을 돌아 Z에 도착할 수 있습니다.

 

         Z만 도착하는 것만 고려하면, '+'가 빠진 곳에는 '3' 블록이 와도 Z에 도달할 수 있습니다.

         하지만 가스가 흐르지 못하는 블록들이 존재하게 되고, 이는 문제 조건에 위배됩니다.

 

         따라서 모든 블록을 돌아주었는 지 확인 작업이 필요합니다. 

 

소스 코드

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <memory.h>


#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

#define SIZE 30

using namespace std;

int r, c, nDir = 4, nTotal = 1;
int dir[4][2] =
{
   { -1, 0 },
   { 1, 0 },
   { 0, -1 },
   { 0, 1 }
};

pair<int, int> startPos;
pair<int, int> emptyPos;

char cResult = 0;
char map[SIZE][SIZE] = { 0 };
char tileList[4][6] =
{
   { '|', '+', '1', '4', 'Z' }, // Up
   { '|', '+', '2', '3', 'Z' }, // Down
   { '-', '+', '1', '2', 'Z' }, // Left
   { '-', '+', '3', '4', 'Z' }, // Right
};

bool clearFlag = false;

bool IsInMap(int x, int y)
{
	return (0 <= x && x < r && 0 <= y && y < c);
}

void DFS(int curX, int curY, int iDir, bool flag, bool visit[][SIZE], int iTotal)
{
	if (!visit[curX][curY])
	{
		visit[curX][curY] = true;
		iTotal++;
	}

	if (map[curX][curY] == '1') 
		iDir = (iDir + 3) % 4;
	else if (map[curX][curY] == '2' || map[curX][curY] == '4') 
		iDir = (iDir + 2) % 4;
	else if (map[curX][curY] == '3') 
		iDir = (iDir + 1) % 4;
	else if (map[curX][curY] == 'Z' && iTotal == nTotal)
	{
		clearFlag = true;
		return;
	}

	int nX = curX + dir[iDir][0];
	int nY = curY + dir[iDir][1];

	if (!IsInMap(nX, nY)) return;

	if (map[nX][nY] != '.')
	{
		bool bTmp = false;

		for (int i = 0; i < 5; ++i)
		{
			if (tileList[iDir][i] == map[nX][nY])
			{
				bTmp = true;
				break;
			}
		}

		if (!bTmp) return;
	}

	// 빈칸
	if (map[nX][nY] == '.' && !flag)
	{
		for (int i = 0; i < 4; ++i)
		{
			// 빈칸에 대입
			map[nX][nY] = tileList[iDir][i];
			// DFS
			DFS(nX, nY, iDir, true, visit, iTotal);
			// 클리어했을 시
			if (clearFlag == true)
			{
				emptyPos.first = nX;
				emptyPos.second = nY;
				cResult = tileList[iDir][i];
				return;
			}
			visit[nX][nY] = false;
			map[nX][nY] = '.';
		}
	}
	else if (map[nX][nY] != '.')
	{
		DFS(nX, nY, iDir, flag, visit, iTotal);
		visit[nX][nY] = false;
	}
		
}

int main()
{
	// 입력
	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			char ch = 0;
			scanf(" %c", &ch);

			map[i][j] = ch;
			if (ch != '.') nTotal++;

			if (ch == 'M')
			{
				startPos.first = i;
				startPos.second = j;
			}
		}
	}

	bool visit[SIZE][SIZE] = { 0 };

	for (int i = 0; i < 4; ++i)
	{
		DFS(startPos.first, startPos.second, i, false, visit, 0);
		if (clearFlag) break;
		memset(visit, 0, sizeof(visit));
	}

	printf("%d %d %c\n", emptyPos.first + 1, emptyPos.second + 1 ,cResult);

	return 0;
}