[SWEA] 1210. [S/W 문제해결 기본] Array2 - Ladder1

문제

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE

SW Expert Academy

 

풀이

이 문제는 처음에는 문제를 잘못 이해하고 DFS로 풀려고 했었다. 이 방식으로 풀려 했더니 스택 오버플로우 에러가 났었었다. 문제 조건을 다시 생각해보니 아래 방향으로 내려가고 있었으면 꺾이는 부분이 나오면 밑으로 계속 갈 수 있어도 그 부분은 방문하지 않아도 되는 것이었다. 이 부분까지 모두 탐색하려다보니 메모리 초과가 났었던 것 같다.

내가 풀었던 방식은 위에서부터 접근하는 것이 아니라 밑에 2라는 목적지부터 거꾸로 올라가는 방법을 택했다. 각 경우마다 조건문을 이용해서 회전하고 위로 올라가면서 시작점을 찾을 수 있도록 구현했다. 좀 지저분한 코드이지만 다른 방법을 더 연구해 봐야겠다.

 

  

import java.util.*;
 
public class Solution {
    static Scanner scan = new Scanner(System.in);
    static int[][] map = new int[100][100];
    static int flag = 0; // 0 : 위, 1 : 왼쪽, 2 : 오른쪽
    static int d_idx = -1;
 
    static void read() {
        scan.nextInt();
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                map[i][j] = scan.nextInt();
                if (map[i][j] == 2)
                    d_idx = j;
            }
        }
    }
 
    static int get_num() {
        int idx = -1;
        int r = 99, c = d_idx;
        while (true) {
            if (r == 0) {
                idx = c;
                break;
            }
            if (flag == 0) {// 위 방향
                if (is_valid(r, c - 1)) {// 왼쪽에 존재
                    c--;
                    flag = 1;
                } else if (is_valid(r, c + 1)) {// 오른쪽에 존재
                    c++;
                    flag = 2;
                } else // 양쪽에 없음
                    r--;
            } else {// 꺾인 상태
                if (flag == 1) {// 왼쪽
                    if (is_valid(r - 1, c)) {
                        r--;
                        flag = 0;
                    } else
                        c--;
 
                } else {// 오른쪽
                    if (is_valid(r - 1, c)) {
                        r--;
                        flag = 0;
                    } else
                        c++;
                }
            }
        }
        return idx;
    }
 
    static boolean is_valid(int r, int c) {
        if ((r >= 0 && r < 100) && (c >= 0 && c < 100) && (map[r][c] != 0))
            return true;
        return false;
    }
 
    static void solution() {
        for (int i = 1; i <= 10; i++) {
            read();
            System.out.println("#" + i + " " + get_num());
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        solution();
    }
 
}