[swea] 1210. Ladder

문제설명

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE&problemTitle=lad&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

기본아이디어

처음 문제를 읽었을 때는 그냥 조건대로 풀었다. 시작점부터 찾아가서 마지막행이 2 이면 찾고 종료 아니면 다시 다음 시작점에서 시작하는 방식으로 풀었다. 

 

하지만 다른 더 좋은 풀이가  있어서 가져왔다. 내 방식과 다른 점은 크게 1. 도착점부터 찾아가는게 다르다  2. 사다리는 결국 일자로 내려오기 때문에 왼쪽 오른쪽 이동할 때 옆의 사다리로 한번에 이동하는게 가능하다. 그런 방식으로 List에 사다리의 번호대로 열번호를 저장해두면 사용 가능합니다.

구현코드

public static void main(String[] args) throws IOException {
 
        int T = 10;
        for(int test_case = 1; test_case <= T; test_case++){
            input.readLine();
            int[][] map = new int[100][];
            StringTokenizer input_str;
            for(int i = 0; i < 100; i++) {
                input_str = new StringTokenizer(input.readLine());
                int[]temp = new int[100];
                for (int j = 0; j < 100; j++)
                    temp[j] = Integer.parseInt(input_str.nextToken());
                map[i] = temp;
            }
 
            for(int i = 0; i < 100; i++){
                if(map[0][i] == 0)
                    continue;
                int r = 0;
                int c = i;
                while(r < 99){
                    if(c+1 < 100 && map[r][c + 1] == 1)
                        do{
                            c++;
                            if(map[r+1][c] == 1) {
                                r++;
                                break;
                            }
                        }while(c+1 < 100 && map[r][c + 1] == 1);
                    else if(c-1 >= 0 && map[r][c -1] == 1)
                        do{
                            c--;
                            if(map[r+1][c] == 1) {
                                r++;
                                break;
                            }
                        }while(c-1 >= 0 && map[r][c -1] == 1);
                    else
                        r++;
                }
                if(map[r][c] == 2){
                    output.append("#" + test_case + " " + i + "\n");
                    break;
                }
            }
        }
        System.out.print(output);
    }
 
 

정리, 기억할 내용

1. 문제를 잘 읽어보고 풀자.

2. 일반화 할 수 있는 내용이 있는지 살펴보자.