[D4] 1210.Ladder1

입력)

총 10개의 테스트 케이스

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

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

 

출력)

# 해당 테스트 케이스 번호, 지정된 도착점에 대응되는 사다리의 y index 출력

입, 출력 분석)

(생략)

 

핵심)

사다리를 그릴 때, 방향을 고려하여 그리는 것이 핵심이다.

한 칸씩 사다리를 타고 내려간다고 가정하고, 1의 여부를
자신의 아래,왼쪽,오른쪽 영역을 탐구한다고 가정했을 때,

 

회전하는 경우는
1) 1의 cnt가 2이고

2) 1인 영역이 (아래 또는 왼쪽), (아래 또는 오른쪽)을 가진다
    따라서 1인 영역을 발견했을 때 key를 두어,
    (아래 또는 왼쪽) : key = 0 + 1 -> 왼쪽

    (아래 또는 오른쪽) : key = 0 + 2 -> 오른쪽

    key < 3 일 때 회전한다.
    (key == 3일 때는 핑크색, cnt 가 2인 경우)

 

현재 어느 방향으로 오고 있었는지(dir) 확인하여, 회전하는 경우에 알맞게 방향을 바꾸면 된다.

 

예시 분석)

(생략)

 

실수) 

- 모든 경우의 수를 저렇게 따져보기 전에 복잡하고 내가 다루지 않았던 유형이라 기피했던 것 같다..
  (질질 끌다가 결국에 할 꺼면서...)

- 설계 초반에 핑크색 경우에서 cnt == 2 일 때를 cnt == 1로 잘못 계산했다.

- while(x<100)에서 x=99일 때 x+=dx[dir]; y+dy[dir]; 때문에 if(map[x][y] == 2)가 제대로 되지 않아서
  if(x==99) break; 문을 넣었다. (사실 map[x-1][y] == 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]);
		}
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0; ans = j;
			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];
			}
			if (map[x][y] == 2) {
				ans = j;	break;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}