[C] Ladder

by SW expert academy 

 

사다리 게임에서 꽝에 도착하게 되는 출발 점을 찾아라. 꽝은 2로 표시한다.

x=4인 출발점에서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향전환을 하게 된다. 방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.

 

 

입력

첫 번째 줄에 test case의 수 T(1<=T<=100)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. '0'으로 채워진 평면상에 사다리는 연속된 '1'로 표현된다. 도착 지점은 '2'로 표현된다.

 

출력

x에 도착하게 되는 출발점의 x좌표를 출력

 

출력 예시

67

3

 

😚 풀이

 

// by SW expert academy
#include<stdio.h>

int search(int Map[102][102], int start) {		# 사다리, 도착지점 x좌표
	int y = 100, x = start;

	while (y != 1) {		# 끝까지 올라갈 때 까지
		if (Map[y][x - 1] == 1)	// 좌측 사다리가 있으면
		{
			while (Map[y][x - 1] != 0) {
				x--;		// 왼쪽 이동
			}
			y--;			// 위로 이동
		}
		else if (Map[y][x + 1] == 1) {		// 우측 사다리가 있으면
			while (Map[y][x + 1] != 0) {
				x++;				// 우측 이동
			}
			y--;				// 위로 이동
		}
		else {
			y--;				// 위로 이동
		}
	}
	return x;
}

int testCase, t;
int i, j;

int main() {
	int Map[102][102];
	int num_of_testcase;
	int target;

	scanf_s("%d", &testCase);

	for (t = 0; t < testCase; t++)
		scanf_s("%d", &num_of_testcase);

	// 사다리 초기화
	for (i = 0; i < 102; i++)
		for (j = 0; j < 102; j++)
			Map[i][j] = 0;

	for (i = 1; i < 101; i++)
		for (j = 1; j < 101; j++)
			scanf_s("%d", &Map[i][j]);

	// 도착 지점 찾기(i의 범위를 1~100으로 고쳐도 됨)
	for(i=0; i<102; i++)
		if (Map[100][i] == 2) {
			target = i;
			break;
		}

	printf("%d\n", search(Map, target) - 1);
	return 0;
}

 

도착점에서 거꾸로 올라간다. 

도착점을 찾은 이후에 좌우에 길이 있는지 살펴 보고 없으면 위로 간다.

좌우에 길이 있다면 끝까지 이동한 뒤 위로 간다.

위 작업을 반복

경계면 처리를 위해 여유 공간을(102) 만들었다.