[D4] 1211. ladder2

추천) 1210. ladder1 문제를 먼저 풀기를 추천한다.

https://masso.tistory.com/23?category=881145

[D4] 1210.Ladder1

 

입력)

총 10개의 테스트 케이스

테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열

(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)

 

출력)

# 해당 테스트 케이스 번호, 가장 짧은 이동 거리를 가지는 사다리의 y index 출력

입, 출력 분석)

입력을 보면 마지막 줄에 존재해야할 2가 없음에 주의해야 한다.

 

핵심)

1210. ladder1 문제 풀이 링크 참고

입력 분석을 통해
- x == 99에 도달할 때까지, 가장 짧은 칸을 이동해온 y index를 구해야 함을 알았다.

 

복수 개인 경우 가장 큰 x좌표
- y(0 -> 99)로 탐색하며, 짧거나 같은 거리를 가지는 사다리가 있을 때 y index를 갱신하면 된다.

 

예시 분석)

(생략)

 

실수) 

- 도착 지점에 도착하는 사다리 중에 짧은 거리를 가지는 사다리를 구하는 문제인 줄 알았는데,가만히 입력을 보니까 2가 없는 것을 알게 되었다. (이래서 사람이 편견이 무섭다)

 

구현)

#include<iostream>
using namespace std;

int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 };  // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽

int main(int argc, char** argv) {
	int test_case, T = 0, ans = 0;
	for (test_case = 1; test_case <= 10; ++test_case) {
		scanf("%d", &T);
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++)
				scanf("%d", &map[i][j]);
		}
		int minLen = 10000; // 0. minLen 정의
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0, len = 1; // 1. len 정의
			while (x < 100) {
				int cnt = 0, key = 0;
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
					if (map[nx][ny]) {
						cnt++;	key += i; // 아래 0, 왼 1, 오 2
					}
				}
				if (cnt == 2 && key < 3) { // 회전
					if (dir == 0) dir = key;
					else dir = 0;
				}
				if (x == 99) break;
				x += dx[dir]; y += dy[dir];	len++; // 2. 총 len 구하기
			}
			if(minLen >= len){ // 3. len 갱신하기
				minLen = len;
				ans = j;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}