[SWEA] 1211. [S/W 문제해결 기본] 2일차 - Ladder2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh

SW Expert Academy

이전의 문제인 Ladder1과 사다리 타는 과정은 동일하나 이번에는 모든 사다리를 타며 이동 거리를 구하고, 최소 이동거리를 가지는 index를 찾아내야 한다.

복수개인 경우에는 가장 큰 index를 답으로 출력해야 하기 때문에 최소 이동거리일 경우 vector에 삽입하고, 만약 최소 이동거리가 갱신될 경우 vector를 clear하고 삽입하고, 끝까지 탐색한 후 vector의 마지막 index에 해당하는 값을 답으로 구했다.

#include <iostream>
#include <ios>
#include <vector>
using namespace std;

int ladder[100][100], cnt, minCnt;
vector<int> tempRes;
int getResult();
void getLaddling(int y, int x);

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	for (int i = 0; i < 10; i++) {
		minCnt = 2e9;
		int tc; cin >> tc;
		for (int y = 0; y < 100; y++) {
			for (int x = 0; x < 100; x++) {
				cin >> ladder[y][x];
			}
		}
		cout << '#' << tc << ' ' << getResult() << "\n";
	}
	return 0;
}

int getResult() {
	for (int i = 0; i < 100; i++) {
		if (ladder[0][i]) {
			cnt = 0;
			getLaddling(0, i);
			if (cnt > minCnt) continue;
			else if (cnt < minCnt) {
				tempRes.clear();
				minCnt = cnt;
				tempRes.push_back(i);
			}
			else tempRes.push_back(i);
		}
	}
	return tempRes[tempRes.size() - 1];
}

void getLaddling(int y, int x) {
	cnt++;
	if (y == 99) return; // 도착

	ladder[y][x] = 0;	// 지나온 곳 0으로 바꾸기

	if (x != 0 && ladder[y][x - 1]) getLaddling(y, x - 1);	// 왼쪽
	else if (x != 99 && ladder[y][x + 1]) getLaddling(y, x + 1);	// 오른쪽
	else getLaddling(y + 1, x);	// 아래

	ladder[y][x] = 1;	// 다시 1로 복구
}