[SWEA] S/W 문제해결 기본(2) - Ladder 2

[1211] Ladder 2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh

• 100 X 100 크기의 2차원 배열로 주어진 사다리에 대해서, 모든 출발점을 검사하여 가장 짧은 이동거리를 반환하는 코드를 작성하라.
• 모든 사다리 경로에 대해 최소 거리 구하는 문제

 

 

Solution

• Ladder 1문제와 달리 지정된 도착점이 아닌 모든 도착점에 대해 사다리 타기를 하고 count가 최소인 출발점 return

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int T, n, m, min, answer;
    static String[][] ladder;
    static int[] dx = { 0, -1, 0 };
    static int[] dy = { -1, 0, 1 };
    static StringTokenizer st;
    static String line;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            T = stoi(br.readLine());
 
            init();
 
            int x = 99, y = 0;
            for (int i = 0; i < 100; i++) {
                ladder[i] = br.readLine().split(" ");
            }
 
            min = Integer.MAX_VALUE;
            for (int i = 0; i < 100; i++) {
                if (ladder[99][i].equals("1")) {
                    y = i;
                    solve(x, y);
                }
            }
 
            System.out.println("#" + T + " " + answer);
 
            if (T == 10)
                break;
        }
 
    }
 
    static void solve(int x, int y) {
        int count = 0;
        int cx = x;
        int cy = y;
        int dir = 1;
        while (cx > 0) {
            // up
            if (dir == 1) {
                cx += dx[dir];
                cy += dy[dir];
                count++;
                // left
                if (cy > 0 && ladder[cx][cy - 1].equals("1")) {
                    dir = 0;
                    continue;
                }
                // right
                else if (cy < 99 && ladder[cx][cy + 1].equals("1")) {
                    dir = 2;
                    continue;
                }
            } else {
                cx += dx[dir];
                cy += dy[dir];
                count++;
                if (cx > 0 && ladder[cx - 1][cy].equals("1")) {
                    dir = 1;
                    continue;
                }
            }
        }
 
        if (min > count) {
            min = count;
            answer = cy;
        }
    }
 
    static void init() {
        ladder = new String[100][100];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}