SW Expert Academy 의 1211번 문제입니다.
사다리 타기 문제 1과 유사하나, 구해야 하는 결과가 다릅니다.
100x100 의 2차원 배열에 사다리로 탈 수 있는 길이 ‘1’로 표시되고, 그렇지 않은 곳은 ‘0’으로 표시되어 input이 주어집니다.
시작점에서 끝점까지 나갈 수 있는 모든 경로들 중 가장 짧은 경로를 갖는 시작점의 x좌표를 출력하는 문제입니다.
따라서 사다리문제 1과는 다르게 모든 출발점을 검사해야 합니다.
- 난이도 : 2
문제 조건
배열의 크기는 100x100 이다.
갈 수 있는 길들은 모두 1로 표시되어 있다. (사다리타기의 사다리 길)
한 막대에서 출발한 가로선이, 다른 막대를 가로질러 연속할 수는 없다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음에는 2차원 배열의 값들이 주어진다.
Output
가장 짧은 경로를 가지는 출발점의 열 번호(x좌표)를 출력한다.
처음에 생각한 아이디어
숫자 ‘1’을 보면서 따라가되 오른쪽 혹은 왼쪽으로 갈 수 있다면,
아래로 먼저 가지 않고 오른쪽 혹은 왼쪽으로 가야 하는 것을 먼저 생각했습니다.
모든 시작점이 될 수 있는 곳에서 출발해서, 지정된 출구로 나가는 길을 찾는 방식을 택했습니다.
그리고 매번 그 경로의 길이를 구해 놓습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define N 100
#define VISIT 1
int main() {
int test_case;
int input = 0;
int rowNum = 0, colNum = 0;
int path_length = 0, min = 9999;
int startPoint = 0, Rflag = 0;
int arr[100][102] = { 0, };
int visit[100][102] = { 0, };
// 양쪽 벽을 값 -1로 초기화
for (int j = 0; j < 100; j++) {
arr[j][0] = -1;
arr[j][101] = -1;
}
for (int T = 0; T < 10; T++) {
scanf("%d", &test_case);
for (int i = 0; i < 100; i++) { // 사다리 데이터 받기
for (int j = 1; j < 101; j++) {
scanf("%d", &input);
arr[i][j] = input;
}
}
for (int k = 1; k < 101; k++) { // 시작 지점이 될 수 있는 총 100 개 중 1인 곳에서 시작한다.
rowNum = 0; colNum = k;
/* 사다리타기 진행 */
if (arr[rowNum][colNum] == 1) {
path_length = 0;
for (int m = 0; m < 100; m++) {
rowNum++; path_length++; // 처음 1회는 무조건 아래로 내려간다.
// 오른쪽으로 갈 수 있을 때까지 간다
while (arr[rowNum][colNum + 1] == 1) {
Rflag = 1;
colNum += 1; path_length++;
}
// 왼쪽으로 갈 수 있을 때까지 간다
// Rflag의 역할은, 오른쪽으로 계속 이동한 이력이 있으면
// 같은 높이에서 왼쪽으로는 갈 수 없도록 하기 위함이다.
if (Rflag != 1){
while (arr[rowNum][colNum - 1] == 1) {
colNum -= 1; path_length++;
}
}
Rflag = 0;
}
if (min >= path_length) {
min = path_length;
startPoint = k - 1;
}
}
}
printf("#%d %d\n", test_case, startPoint);
min = 9999;
}
}