Ladder1
1. 문제 접근 및 아이디어
사다리 타기의 핵심은 좌/우 길이 있으면 무조건 꺽어야 한다 것입니다.
- 역발상 (Bottom-up)
- 모든 출발점에서 시작해 도착점을 찾는 것보다, 도착점에서 시작해 위로 올라가 0행의 열 번호를 찾는 것이 훨씬 빠릅니다.
- 우선순위 결정
- 현재 위치에서 갈 수 있는 방향은 좌, 우, 상입니다.
- 이때 좌/우에 길이 있다면 위로 올라가는 것보다 좌/우 이동이 우선되어야 합니다.
접근 순서
- 100x100 배열에 사다리 정보를 입력받으면서 값이 2인 도착점의 좌표를 저장합니다.
- 배열의 행이 0(최상단)이 될 때까지 반복문을 돌립니다.
- 현재 위치에서 좌측이나 우측에 1이 있는지 체크합니다.
- 옆길이 있다면 그 길이 끝날 때까지 이동합니다.
- 옆길이 없거나 이동이 끝나면 위로 한 칸 이동합니다.
2. 필요 개념 및 알고리즘
- 시뮬레이션
- 주어진 사다리 타기 로직을 그대로 코드로 구현해야 하는 문제입니다.
- 문제에서 이동 경로에 대한 명확한 조건을 제시하고 있습니다.
- 역방향 탐색
- 모든 출발점과 하나의 도착점이 있어서, 거꾸로 추적하는 것이 훨씬 효율적 입니다.
3. 어려웠던 점
- 무한 루프
- 좌/우 이동 후 다시 위로 올라가지 않고 옆으로만 왔다 갔다 하거나, 이미 지나온 길을 다시 돌아가는 로직을 구현할 때 발생합니다.
- 순서 오류
- 좌/우 탐색보다 위로 가는 로직을 먼저 처리하면 옆길을 무시하고 지나칠 수 있습니다.
- 반드시 좌/우 확인이 우선되어야 합니다.
- 좌표 체계
- 문제에서 주어진 (x,y) 관념이 배열의 [row][col]과 햇갈릴 수 있습니다.
4. 코드 풀이
4.1 핵심 로직
while (r > 0) {
if (왼쪽 길인가?) {
// 왼쪽 끝까지 이동 (r은 그대로)
}
else if (오른쪽 길인가?) {
// 오른쪽 끝까지 이동 (r은 그대로)
}
// [핵심 포인트]
// 왼쪽으로 갔든, 오른쪽으로 갔든, 아니면 옆길이 없었든
// if-else if 문이 끝나면 "무조건" 위로 한 칸 올라갑니다.
r--;
}
- 동작 원리: 좌/우로 끝가지 이동한 직후, if-else if 문을 빠져나오자마자 r–를 만나서 바로 윗줄로 올라가 버립니다.
- 결과: 다음 while 루프가 시작될 떄는 이미 행이 바뀐 상태이기 때문에, 방금 지나온 옆길을 다시 검사하며 무한 루프할 일이 없습니다.
4.2 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// tc 수행
for (int tc = 1; tc <= 10; tc++) {
// 테스트 케이스의 번호 입력
int num = Integer.parseInt(br.readLine().trim());
// 사다리 정보 배열 초기화
int map[][] = new int[100][100];
// 도착점
int end_r = -1;
int end_c = -1;
// 사다리 정보 입력
for (int i = 0; i < 100; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 100; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 도착점 계산
if (map[i][j] == 2) {
end_r = i;
end_c = j;
}
}
}
// 처리
int result = -1; // 도착하게 되는 출발점의 x좌표
// 행이 0이 되면 수행 종료
while (end_r > 0) {
// 왼쪽 탐색
if (0 <= end_c - 1 && map[end_r][end_c - 1] == 1) {
while (0 <= end_c - 1 && map[end_r][end_c - 1] == 1) {
end_c--;
}
}
// 오른쪽 탐색
else if (end_c + 1 < 100 && map[end_r][end_c + 1] == 1) {
while (end_c + 1 < 100 && map[end_r][end_c + 1] == 1) {
end_c++;
}
}
// 왼쪽 또는 오른쪽에 자리가 없을 때 직진
// 왼쪽 또는 오른쪽 탐색 후 자리가 없을 때 직진
end_r--;
}
result = end_c;
// 출력 내용 추가
sb.append("#" + num + " " + result + "\n");
} // tc 종료
// 출력
System.out.println(sb);
}
}