[SW expert Academy] SWEA 1211번 Ladder2 자바(Java)

[D4] [S/W 문제해결 기본] 2일차 - Ladder2 - 1211

문제 링크

성능 요약

메모리: 31,400 KB, 시간: 144 ms, 코드길이: 2,236 Bytes

제출 일자

2023-12-30 02:42

 

풀이 방법

1. 출발 지점에서 사다리 발견시 dfs로 내려가준다.

2. 내려가면서 count

3. 내려가는 도중 오른쪽,왼쪽에 사다리 발견시 이동하면서 Count

4. 맨 아래까지 내려간 뒤 더 적거나 같으면 갱신해준다.(가장 큰 값을 출력하라고 했으므로)

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

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

class Solution {
    static int[][] map;
    static int distance, answer;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            br.readLine();
            // 사다리 배열
            map = new int[100][100];
            for (int i = 0; i < map.length; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < map.length; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            // distance : 최소값을 구하기 위해 최대값으로 초기화
            distance = Integer.MAX_VALUE;
            answer = 0;
            // 출발 지점 마주치면 시작
            for (int i = 0; i < map.length; i++) {
                if (map[0][i] == 1) {
                    dfs(i);
                }
            }
            sb.append("#" + tc + " " + answer).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int start) {
        // (0,start)에서 시작
        int x = 0;
        int y = start;
        // 총 이동거리를 저장 할 count
        int count = 0;
        // map 거리만큼 이동
        while (x < map.length) {
            // 왼쪽에 사다리 존재시 쭉 이동한다.
            if( y - 1 >= 0 && map[x][y-1] == 1){
                while(y - 1 >= 0 && map[x][y-1] == 1){
                    y--;
                    count++;
                }
            }
            // 오른쪽에 사다리 존재시 쭉 이동해준다.
            else if (y + 1 < map.length && map[x][y + 1] == 1) {
                while (y + 1 < map.length && map[x][y + 1] == 1) {
                    count++;
                    y++;
                }
            }
            // 이동 후 한칸 내려감과 동시에 count++
            x++;
            count++;
        }

        // distance 갱신 가능하다면 해줌.
        if (distance >= count) {
            distance = count;
            answer = start;
        }
    }
}