[코딩 테스트 RUN] SWEA 수업 : 1210. Ladder 1

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

 

[SW Expert Academy] 1210. Ladder1

SW Expert Academy

 

사다리 문제. 이 문제의 핵심은 바로 방향이다. 위에서부터 찾지 말고 아래 골인지점에서 찾는 쪽이 압도적으로 좋다. 이번 문제는 어렵기 때문에(D4), 차근차근 풀어나가보자.

 

일단 2의 위치를 찾는다. 2는 사다리 특성 상 사다리의 맨 아래에 있다. 즉, [99]에서 순회하면서 찾으면 된다.

 

int r = 99;
int c = 0;
for (int i = 0; i < 100; i++) {
    if(arr[99][i] == 2){
    c = i;
    }
}

 

그리고 사다리는 1 혹은 0이다. 갈 수 있다면 1을, 아니라면 0이 된다. 여기서 사다리 방향을 어떻게 할까? 결국 골인 지점에서는 갈 수 있는 길이 얼마 되지 않는다. 특히 골인에 들어갈 수 있는 경우의 수는 얼마 채 되지 않는다.

일단 왼쪽 혹은 오른쪽을 살펴본다. 그곳에 길이 있으면 그쪽으로 나아간다. 끝까지 간 뒤, 그곳에 길이 없으면 그때 올라가는 것이다.

 

좌우는 c고, 위아래는 r로 취급한다. r은 올라가는 것밖에 없으므로 가산될 일은 없다.

 

따라서 아래와 같은 식이 된다.

 

if(c - 1>= 0 && arr[r][c - 1] == 1){ //1이라면 전진
    while(c - 1>= 0 && arr[r][c - 1] == 1){
    	c--;
    }
    r--;
} else if(c + 1 < 100 && arr[r][c + 1] == 1){
    while(c + 1 < 100 && arr[r][c + 1] == 1){
    	c++;
    }
    
    r--;
} else {
    r--;
}

 

 

여기서 경계 체크를 잊지 말아야 한다. 경계 체크를 하지 않으면 바로 오류가 나기 때문. 안에 있는 while도 해두는 쪽을 추천한다.

그리고 이걸 r이 0이 될 때까지 반복하면 되기 때문에, 밖에 while문을 사용하면 된다.

 

정답

package SWEA.Ladder1;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int test_case = 1; test_case <= 10; test_case++) {
            // 테스트 케이스 분할
            int T = Integer.parseInt(br.readLine());

            int[][] arr = new int [100][100];

            for (int i = 0; i < 100; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 100; j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            //tokenizer로 배열 할당 성공
            int r = 99;
            int c = 0;
            for (int i = 0; i < 100; i++) {
                if(arr[99][i] == 2){
                    c = i;
                }
            }

            while(r > 0) {
                if(c - 1>= 0 && arr[r][c - 1] == 1){ //1이라면 전진
                    while(c - 1>= 0 && arr[r][c - 1] == 1){
                        c--;
                    }
                    r--;
                } else if(c + 1 < 100 && arr[r][c + 1] == 1){
                    while(c + 1 < 100 && arr[r][c + 1] == 1){
                        c++;
                    }
                    r--;
                } else {
                    r--;
                }
            }

            System.out.printf("#%d %d%n", test_case, c);


        }
    }
}