사다리 게임
slipp 사이트를 보다보니 사다리 게임 문제가 있어서 한번 풀어봤다.
내용은 즉 이렇다.
위 그림은 커피 내기를 할 때 유용한 사다리 게임입니다.
잘 생각해 보면, 사다리 게임은 가로선을 (높이, 왼쪽의 세로줄 번호) 형태로 나타낼 수 있습니다.
예컨대, 위 사다리 게임은 (1, 1), (6, 1), (9, 1), (3, 2), (5, 2) ....와 같이 표현할 수 있습니다.
보면 시작점만 (1,1) 이런 형태로 넣고 있다. 그래서 끝점 (1,2) 도 알아야 2에서 1로 갈 수 있을텐데...
그런데 가만보면 시작과 끝점 형태를 보면
(x,y) 시작점 ,
(x,y+1)이 끝점이 된다.
어떻게 하면 풀 수 있을까 하다가 깊이우선탐색 혹은 너비우선탐색에 쓰이던 인접행렬이 떠올랐다.
그래서 (1,1)을 넣을때 (1,2)도 같이 넣어 주면 된다고 생각했다.
일단 그래서 코딩을 시작했다.
temp[1][1] = temp[1][2]= 1;
temp[6][1] = temp[6][2]= 1;
temp[9][1] = temp[9][2]= 1;
temp[3][2] = temp[3][3]= 1;
temp[5][2] = temp[5][3]= 1;
temp[8][2] = temp[8][3]= 1;
temp[4][3] = temp[4][4]= 1;
temp[7][3] = temp[7][4]= 1;
temp[10][3] =temp[10][4]= 1;
temp[2][4] = temp[2][5]= 1;
temp[6][4] = temp[6][5]= 1;
temp[8][4] = temp[8][5]= 1;
temp[3][5] = temp[3][6]= 1;
temp[5][5] = temp[5][6]= 1;
temp[7][5] = temp[7][6]= 1;
일단 하드 코딩...
이런식의 코드가 완성되었다.
그리고 또 생각을 했다. 일단 체크는 했는데....흠!
가만보니까 (x,y) 중 y는 내가 현재 갈 위치를 말하는거 같았다.
일단 최초의 값(입력 값)을 index라 했고 만약 [x][index]의 값이 1이라면 선이 그어져 있다고 생각했다.
그리고 오른쪽으로 갈지 왼쪽으로 갈지 결정을 해야 되서 index-1이라면 왼쪽 그렇지 않다면 오른쪽으로 가야 된다.
그래서 나온게 일단 이거다.
for (int i = 0; i < temp.length; i++) {
if(temp[i][index] == 1){
if(temp[i][index - 1] == 1){
index--;
}else{
index++;
}
}
}
테스트를 해봤다. 잘된다.
그런데 몇개 테스트하는중 이상한 걸 발견했다.
내 소스가 틀린것이다.
살펴보니까 단단히 문제가 있었다.
저기 사다리로 보면 (8,4)의 해당 하는 지점이다. (8,4)에선 오른쪽 왼쪽 전부 선이 그어져있다고 생각한다.
왜냐면 (8,3) 도 1이라 체크 해놨고 (8,5) 도 1이라 체크 해놨기 때문이다.
그래서 먼저 걸리는 선한테 그냥 가버린다.
문제다.
그래서 그냥 간단히 생각했다.
시작점과 끝점을 분리하자!.
그래서 이렇게 됐다.
for (int i = 0; i < arr.length; i++) {
if (arr[i][index] == 1 || arr[i][index] == 2) {
if (arr[i][index - 1] == 1 && arr[i][index] == 2) {
index--;
} else {
index++;
}
}
}
끝점을 2로 표시 해두었다.
그래서 해당점이 끝점이라면 오른쪽으로 갈 수 없다.
- 1 또는 2가 체크 되어 있다면
- index - 1이 체크 되어있고 index 가 2라면 왼쪽으로 간다.
- 그게 아니라면 오른쪽으로 이동한다.
이로써 된거 같다.
class Ladder {
private int[][] arr;
Ladder(int length) {
arr = new int[length][length];
}
void add(int a, int b) {
arr[a][b] = 1;
arr[a][b + 1] = 2;
}
int start(int index) {
for (int i = 0; i < arr.length; i++) {
if (arr[i][index] == 1 || arr[i][index] == 2) {
if (arr[i][index - 1] == 1 && arr[i][index] == 2) {
index--;
} else {
index++;
}
}
}
return index;
}
}
Ladder ladder = new Ladder(15);
ladder.add(1, 1);
ladder.add(6, 1);
ladder.add(9, 1);
ladder.add(3, 2);
ladder.add(5, 2);
ladder.add(8, 2);
ladder.add(4, 3);
ladder.add(7, 3);
ladder.add(10, 3);
ladder.add(2, 4);
ladder.add(6, 4);
ladder.add(8, 4);
ladder.add(3, 5);
ladder.add(5, 5);
ladder.add(7, 5);
System.out.println(ladder.start(3));
전체 소스다.
해당 소스가 문제가 된다면 삭제하겠습니다.
출처 :
http://synapsoft.co.kr/jsp/recruit/14t.html