2일차 - Ladder1

내가 이거 풀었을때 내가 기존의 풀이방식(BFS)로 푼 방식으로 했을때 뭐가 문제인지 잘모르겟음.

테스트케이스 만든건 제대로 나옴,
[안되는 내 소스]

#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;


int MAXSIZE = 7;

int arr[100][100] = { 0, };
int chk[100][100] = { 0, };
int dirX[3] = { -1, 1, 0 };//좌, 우, 하강
int dirY[3] = { 0,0,1 };//좌, 우, 하강  위로가는 경우는 없음.
vector<int> vResult;

void BFS(int y, int x)//먼저 좌 -> 우 // 좌, 우 길 없을때 하강한다.
{
	chk[y][x] = 1;
	queue<pair<int,int>> qTemp;
	qTemp.push(make_pair(x, y));

	while (!qTemp.empty())
	{
		int x = qTemp.front().first;
		int y = qTemp.front().second;
		qTemp.pop();

		int iFlag = 0;
		for (int i = 0; i < 3; i++)//좌 우 하강 우선순위입니다.
		{
			int nx = x + dirX[i];
			int ny = y + dirY[i];

			if (nx >= 0 && nx <MAXSIZE  && ny >= 0 && ny < MAXSIZE)//바운더리 내에 들고
			{
				if ( ((1 == arr[ny][nx]) && (0 == chk[ny][nx])) || (arr[ny][nx] == 2))//좌 또는 우가 1로 연결되어있고, 방문 안했을 시
				{
					if (arr[ny][nx] == 2)
					{
						vResult.push_back(nx);
						vResult.push_back(ny);
						chk[ny][nx] = 1;
						return;
					}

					iFlag = 1;
					chk[ny][nx] = 1;
					qTemp.push(make_pair(nx, ny));
				}

				if (((i == 2) && (iFlag = 0) && (0 == chk[ny][nx])) && (1 == arr[ny][nx]) || (arr[ny][nx] == 2) )//여기 왔을땐 iFlag 필터링 안됬을때임.
				{
					if (arr[ny][nx] == 2)
					{
						vResult.push_back(nx);
						vResult.push_back(ny);
						chk[ny][nx] = 1;
						return;
					}

					
					chk[ny][nx] = 1;
					qTemp.push(make_pair(nx, ny));
				}
			}
		}
	}
}



int main(void)
{
	for (int i = 0; i < 10; i++)//전체 테스트케이스
	{
		for (int j = 0; j < MAXSIZE; j++)
		{
			for (int k = 0; k < MAXSIZE; k++)
			{
				int iTemp; cin >> iTemp;
				arr[j][k] = iTemp;
			}
		}

		for (int j = 0; j < MAXSIZE; j++)//맨 윗줄에서 부터 시작합니다. 0행부터 0열~99열까지 가는 내용
		{
			if (1 == arr[0][j])//1인경우만
			{
				BFS(0, j);//각각의 줄에서 BFS탐색 시작합니다.

				if (vResult.size() > 1)
				{
					if (2 == arr[vResult[1]][vResult[0]])
					{
						cout << "#" << i + 1 << " " << j + 1 << endl;
						vResult.clear();
						break;
					}
				}				
			}
		}

		for (int j = 0; j < MAXSIZE; j++)
		{
			for (int k = 0; k < MAXSIZE; k++)
			{
				chk[j][k] = 0;
			}
		}
	}
	return 0;
}

[되는 소스]
백트래킹

#include<iostream>
#include<vector>
#include<string.h>

using namespace std;

int ladder[100][100];
int check[100][100];
int dir[3][2] = { {0, -1}, {0, 1}, {-1, 0} };
int start;
int answer;

// 도착점에서부터 역으로 출발 좌표를 찾아간다
void backTracking(int x, int y) {
	if (x == 0) {
		answer = y;
		return;
	}

	for (int i = 0; i < 3; i++) {
		int new_x = x + dir[i][0];
		int new_y = y + dir[i][1];

		if (new_x < 0 || new_y < 0 || new_x >= 100 || new_y >= 100) continue;

		if (ladder[new_x][new_y] == 1 && check[new_x][new_y] == false) {
			check[new_x][new_y] = true;
			backTracking(new_x, new_y);
			return;
		}
	}
}

int main() {
	for (int t = 0; t < 10; t++) {
		int T;
		cin >> T;
		start = 0;
		answer = 0;
		memset(check, false, sizeof(check));
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				cin >> ladder[i][j];
				if (i == 99 && ladder[i][j] == 2) {
					start = j;
				}
			}
		}

		backTracking(99, start);
		
		cout << "#" << T << " " << answer << endl;
	}
	return 0;
}