<백준알고리즘>16954번 DFS알고리 관련

백준 16954번

접근방법

가장 먼저 든 생각은 DFS나 BFS를 이용하여 하는 것 같다는 생각이었고 저번엔 BFS를 써서 이번엔 DFS를 사용하였다.
두 번째로 고려한 것은 이동방향이 제자리 상하좌우 대각선인 점을 고려하여 DFS를 진행해야 한다는 점이다.
세 번째론 방향 이동후에 벽을 밑으로 이동시키며 겹치는지 아닌지를 검사하는 것이다.
네 번째론 8칸이 최대 길이이므로 cnt가 9이상이 온다는 것은 벽이 이미 다 내려갔다는 것이므로 무조건 탙출 가능하므로 이 점을 고려하여 시간을 줄였다.

시간이 걸린 이유

왜인지 계속해서 오답이 나왔는데 벽을 내릴때 r을 기준으로 반대로 해야(8부터 1로) 벽이 같은 c에 1칸 차이로 존재할 때도 정상적인 동작을 한다는 것을 늦게 캐치했다.

벽

벽
이런 식일 경우

하나씩 디버깅 해보다가 발견하였다.

코드가 살짝 더러워 보이는데 좀 깔끔하게 하는 것도 연습해야겠다..

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

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

int dxx[9] = {0, -1,1,0,0 ,-1,-1,1,1 };
int dyy[9] = {0, 0, 0, 1, -1 ,1,-1,1,-1};
int isVisited[9][9] = { 0 };
int cnt = 0;
int ans = 0;

bool MoveWall(int m[9][9],int cy, int cx)
{
	bool isOverlapped = false;

	queue <pair<int, int>> Q;

	for (int i = 8; i >= 1; i--)
	{
		for (int j = 1; j <= 8; j++)
		{
			if (m[i][j] == 1)
			{
				if (i + 1 == cy && j == cx)
					isOverlapped = true;

				if (i < 8)
				{
					m[i + 1][j] = 1;
				}
				m[i][j] = 0;
			}
		}
	}


	return isOverlapped;
}


void BT(int m[9][9], int curY, int curX,int move,int cnt)
{

	if (ans == 1)
	{
		return;
	}

	int ny = 0;
	int nx = 0;

	ny = curY + dyy[move];
	nx = curX + dxx[move];

	if (ny > 8 || nx > 8 || ny < 1 || nx < 1 || m[ny][nx] == 1  || isVisited[ny][nx] == 1)
		return;

	if (ny == 1 && nx == 8 || cnt >=9)
	{
		ans = 1;
		return;
	}


	int arr[9][9];
	memcpy(arr, m, sizeof(arr));

	if (MoveWall(arr,ny,nx))
		return;

	for (int i = 0; i < 9; i++)
	{
		isVisited[ny][nx] = 1;
		BT(arr, ny, nx,i,cnt+1);
		isVisited[ny][nx] = 0;
	}



}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int orig[9][9];

	for (int i = 1; i <= 8; i++)
	{
		for (int j = 1; j <= 8; j++)
		{
			char a;
			cin >> a;

			if(a == '#')
				orig[i][j] = 1;
			else
				orig[i][j] = 0;
		}
	}


	
		for (int i = 0; i < 9; i++)
		{
			BT(orig, 8, 1, i,0);
			cnt++;
		}
	

	cout << ans;

	return 0;
}