[C++] 삼성 1210. [S/W 문제해결 기본] 2일차 - Ladder1

(30분) 문제 푸는데는 10분도 안걸렸는데 이거 입력받는 방식이 평소 문제하고 달라서 계속 틀렸었음.(한 문제 풀때마다 테스트 번호를 입력받게 해놈...)

아이디어는 그냥 도작점에서부터 백트레킹해서 출발점 찾기

 

#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;
}