SW 1824. 혁진이의 프로그램 검증

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE#;return%20false;

SW Expert Academy

 

 

1. 완전 탐색을 해야 하는 이유는 오직 '?' 때문이다 같은 확률로 사방으로 가는 케이스 때문에 

각 케이스별로 경로 탐색을 해야 하는데,

2. BFS를 사용하면 안되는 이유는 예를들어 상 하 좌 우로 흩어진다고 하면 상이 찍고가는 자취가 하에게 영향을 미침.

백트래킹이 필요하므로 DFS를 사용해야 한다.

 

3. 종료는 y,x에서 dir 방향에 mem값으로 지나간 자취가 있는데 동일하게 지나간다면 반복이 되는 케이스 

4. 백트래킹을 사용해 주기 위해 DFS를 사용하니 당연히 일반적인 자취에 대해서는 지워야 하는게 정상.

그러나 ?에 대한 기록도 지울 필요가 있을까?

자취를 지우는 이유는 사방으로 흩어진 4개의 경로 탐색이 서로의 간섭을 받지 않기 위해선데,

1,1의 2방향 4를 가질때 ?를 밟았다는 기록을 지우면 만약 같은 방식으로 또 ?밝으면 또 4방향으로 흩어질 것이기 때문에 기록을 지우는 것은 ? 이외의 것들에 대해서만 진행.

 

 

 

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

int R, C;
string str[20];
bool visit[20][20][16][4];

// 0 상 1 하 2 좌 3 우 

struct Node {

	int y;
	int x;
	int dir;
	int mem;
};

bool flag;

void DFS(int yp, int xp, int dirp, int memp,int cur)
{
	int y, x, dir, mem;

	y = yp;
	x = xp;
	dir = dirp;
	mem = memp;

	char c = str[y][x];
	

	if (c == '@')
	{
		flag = true;
		return;
	}

	if (visit[y][x][mem][dir])
	{
		return;
	}


	visit[y][x][mem][dir] = true;

	if (c == '?')
	{
		if (x - 1 >= 0)
		{
			DFS(y, x - 1, 2, mem,cur+1);
		}
		else
		{
			DFS(y, C - 1, 2, mem, cur + 1);
		}

		if (x + 1 < C)
		{
			DFS(y, x + 1, 3, mem, cur + 1);
		}
		else
		{
			DFS(y, 0, 3, mem, cur + 1);
		}

		if (y - 1 >= 0)
		{
			DFS(y - 1, x, 0, mem, cur + 1);
		}
		else
		{
			DFS(R - 1, x, 0, mem, cur + 1);
		}

		if (y + 1 < R)
		{
			DFS(y + 1, x, 1, mem, cur + 1);
		}
		else
		{
			DFS(0, x, 1, mem, cur + 1);
		}
	}
	else
	{
		if (c - '0' >= 0 && c - '0' <= 9)
		{
			mem = c - '0';

		}
		else if (c == '+')
		{
			if (mem == 15)
			{
				mem = 0;
			}
			else
			{
				mem++;
			}
		}
		else if (c == '-')
		{
			if (mem == 0)
			{
				mem = 15;
			}
			else
			{
				mem--;
			}
		}
		else if (c == '>')
		{
			dir = 3;
		}
		else if (c == '<')
		{
			dir = 2;
		}
		else if (c == '^')
		{
			dir = 0;
		}
		else if (c == 'v')
		{
			dir = 1;
		}
		else if (c == '_')
		{
			if (!mem)
			{
				dir = 3;
			}
			else
			{
				dir = 2;
			}
		}
		else if (c == '|')
		{
			if (!mem)
			{
				dir = 1;
			}
			else
			{
				dir = 0;
			}
		}
		else if (c == '.')
		{

		}


		if (dir == 0)
		{
			if (y - 1 >= 0)
			{
				DFS(y - 1, x, dir, mem, cur + 1);
			}
			else
			{
				DFS(R - 1, x, dir, mem, cur + 1);
			}
		}
		else if (dir == 1)
		{
			if (y + 1 < R)
			{
				DFS(y + 1, x, dir, mem, cur + 1);
			}
			else
			{
				DFS(0, x, dir, mem, cur + 1);
			}

		}
		else if (dir == 2)
		{
			if (x - 1 >= 0)
			{
				DFS(y, x - 1, dir, mem, cur + 1);
			}
			else
			{
				DFS(y, C - 1, dir, mem, cur + 1);
			}
		}
		else if (dir == 3)
		{
			if (x + 1 < C)
			{
				DFS(y, x + 1, dir, mem, cur + 1);
			}
			else
			{
				DFS(y, 0, dir, mem, cur + 1);
			}
		}

		
		visit[y][x][mem][dir] = false;
	}
	

}



int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> R >> C;

		for (int i = 0; i < R; i++)
		{
			cin >> str[i];
		}
		memset(visit, 0, sizeof(visit));
		flag = false;
		DFS(0, 0, 3, 0,0);


		if (flag)
		{
			cout << "#" << test_case << " " << "YES" << endl;
		}
		else
		{
			cout << "#" << test_case << " " << "NO" << endl;
		}

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}