SW Expert Academy 의 1210번 문제입니다.
사다리 타기 문제입니다.
100x100 의 2차원 배열에 사다리로 탈 수 있는 길이 ‘1’로 표시되고, 그렇지 않은 곳은 ‘0’으로 표시되어 input이 주어집니다.
맨 마지막 출구는 배열에 ‘2’로 표시되어 있으며, 출구로 나갈 수 있는 출발점의 열 번호를 출력하는 문제입니다.
조건문과 반복문의 혼합 형태로 어렵지 않게 짤 수 있다고 생각합니다.
- 난이도 : 2
문제 조건
배열의 크기는 100x100 이다.
갈 수 있는 길은 1로 표시되어 있다. (사다리타기의 사다리 길)
input data에서 맨 마지막 행에 출구는 ‘2’로 표시되어 있다.
한 막대에서 출발한 가로선이, 다른 막대를 가로질러 연속할 수는 없다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음에는 2차원 배열의 값들이 주어진다.
Output
출구로 나갈 수 있는 출발점의 열 번호(x좌표)를 출력한다.
처음에 생각한 아이디어
숫자 ‘1’을 보면서 따라가되 오른쪽 혹은 왼쪽으로 갈 수 있다면,
아래로 먼저 가지 않고 오른쪽 혹은 왼쪽으로 가야 하는 것을 먼저 생각했습니다.
그래서 처음에는 모든 시작점이 될 수 있는 곳에서 출발해서, 지정된 출구로 나가는 길을 찾는 방식을 택했습니다.
소스코드 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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <algorithm>
#define N 100
#define VISIT 1
using namespace std;
int main() {
int test_case;
int input = 0;
int point = 0;
int flag = 0;
int rowNum = 0;
int colNum = 0;
int findFlag = 0;
int arr[100][100] = { 0, };
int visit[100][100] = { 0, };
for (int T = 0; T < 10; T++) {
cin >> test_case;
for (int i = 0; i < 100; i++) { // 일단, 사다리 데이터 받기
for (int j = 0; j < 100; j++) {
cin >> input;
arr[i][j] = input;
}
}
for (int i = 0; i < 100; i++) { // visit 배열 초기화
for (int j = 0; j < 100; j++) {
visit[i][j] = 0;
}
}
findFlag = 0;
for (int k = 0; k < 100; k++) { // 시작 지점이 될 수 있는 총 100 개 중 1인 곳에서 시작한다.
rowNum = 0;
colNum = k;
/* 사다리타기 진행 */
if (arr[rowNum][colNum] == 1) { // 처음 1회는 무조건 아래로 내려간다.
rowNum++;
visit[rowNum][colNum] = VISIT; // 방문한 곳은 3으로 표시한다.
while (1) {
/* 위치상 왼쪽 끝 벽이면 오른쪽 혹은 아래로만 갈 수 있다.*/
if (colNum == 0) {
if (arr[rowNum][colNum + 1] != 0 && visit[rowNum][colNum + 1] != VISIT) {
colNum += 1;
visit[rowNum][colNum] = VISIT;
}
else if (arr[rowNum + 1][colNum] != 0 && visit[rowNum + 1][colNum] != VISIT) {
rowNum += 1;
visit[rowNum][colNum] = VISIT;
}
}
else if (colNum == 99) {
if (arr[rowNum][colNum - 1] != 0 && visit[rowNum][colNum - 1] != VISIT) {
colNum -= 1;
visit[rowNum][colNum] = VISIT;
}
else if (arr[rowNum + 1][colNum] != 0 && visit[rowNum + 1][colNum] != VISIT) {
rowNum += 1;
visit[rowNum][colNum] = VISIT;
}
}
else {
if (arr[rowNum][colNum - 1] != 0 && visit[rowNum][colNum - 1] != VISIT) {
colNum -= 1;
visit[rowNum][colNum] = VISIT;
}
else if (arr[rowNum][colNum + 1] != 0 && visit[rowNum][colNum + 1] != VISIT) {
colNum += 1;
visit[rowNum][colNum] = VISIT;
}
else if (arr[rowNum + 1][colNum] != 0 && visit[rowNum + 1][colNum] != VISIT) {
rowNum += 1;
visit[rowNum][colNum] = VISIT;
}
}
if (rowNum == 99 && arr[rowNum][colNum] == 2) {
cout << "#" << test_case << " " << k << endl;
findFlag = 1;
break;
}
else if (rowNum == 99 && arr[rowNum][colNum] != 2) {
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
visit[i][j] = 0;
}
}
break;
}
}
}
if (findFlag == 1)
break;
}
}
}
다시 생각한 아이디어
그런데 다른 분들의 결과와 비교해 보니, 코드 길이가 짧은 분들도 많았고, 실행 시간 차이도 많이 났습니다.
왜 그렇게 차이가 날 수 밖에 없을까 고민하였고 다음과 같이 고쳐보기로 했습니다.
굳이 모든 가능한 시작점에서 사다리타기를 전부 진행할 필요가 없다. 지정된 출구에서 시작해 거꾸로 사다리타기를 하여 출발점을 찾으면, 전체 반복문의 횟수가 줄어든다.
표준 입출력을 c++의 cin, cout으로 하지 않고, stdio.h 의 scanf, printf로 바꿔 본다.
소스코드 2 - 출구에서 거꾸로 출발점을 찾기
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
#include <stdio.h>
int main() {
int test_case;
int input = 0;
int rowNum = 0, colNum = 0;
int destX = 0;
int arr[102][102];
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 102; j++)
arr[i][j] = -1;
}
for (int T = 0; T < 10; T++) {
scanf("%d",&test_case);
for (int i = 1; i <= 100; i++) { // 일단, 사다리 데이터 받기
for (int j = 1; j <= 100; j++) {
scanf("%d",&input);
arr[i][j] = input;
if (input == 2)
destX = j; // 출구를 기록해 놓는다.
}
}
rowNum = 99; colNum = destX; // 맨 처음에는 무조건 위로 올라간다.
arr[rowNum][colNum] = 3; // 방문한 곳은 3으로 표기한다.
while (rowNum != 1) {
if (arr[rowNum][colNum - 1] == 1) { // (1) 왼쪽으로 갈 수 있으면
colNum -= 1;
arr[rowNum][colNum] = 3;
}
else if (arr[rowNum][colNum + 1] == 1) { // (2) 오른쪽으로 갈 수 있으면
colNum += 1;
arr[rowNum][colNum] = 3;
}
else if (arr[rowNum - 1][colNum] == 1) { // (3) 위쪽으로 갈 수 있으면
rowNum -= 1;
arr[rowNum][colNum] = 3;
}
}
printf("#%d %d\n",test_case,colNum-1);
}
}
갈 수 없는 양 벽을 위해 맨 처음에 배열을 -1로 초기화 하였습니다.
- 소스코드 1처럼 불필요하게 visit 배열을 선언할 필요 없이, 지나갈 때마다 지나간 경로에 3이라 표기해서 역할을 대체하였습니다.
- 소스코드 2로 바꾸니 1과 비교해 코드 길이가 훨씬 간결해졌고, 실행 속도도 2배 가량 감소했습니다.
- 다만 실행 속도 차이를 크게 줄여 줄 수 있던 요인은 scanf, printf의 사용 덕분이었습니다.
- 반복문의 횟수는 분명 줄었지만, 이것이 실행 속도에 아주 크게 영향을 미치지는 않았습니다.
- 실행속도를 줄이기 위한 차원에서는 다른 알고리즘을 좀 더 생각해 볼 만 한 문제입니다.
- 코드를 좀 더 고칠 수 있는 방안은 다음과 같습니다.
- 지금은 현재 내 위치에서 왼쪽, 오른쪽, 위쪽 중 가능한 길로 가는 방식입니다.
- 다른 방식은, 큰 for문은 매 회마다 위쪽으로 올라가되, 그 안에서 왼쪽 혹은 오른쪽으로 갈 수 있다면 계속 그 방향으로 나아가는 방식입니다. 즉 갈 데가 없으면 위로 가는 방식입니다.
이렇게 한다면 visit과 같이 방문 flag를 사용하지 않아도 될 것입니다.
이것이 가능한 이유는 사다리의 한 가로선이 다른 가로선과 연결되어 있지 않기 때문에, 경로는 무조건 오른쪽 아니면 왼쪽으로 갈 수밖에 없기 때문입니다.