<Algorithm> 195. Ladder1(SWExpet)

1. Ladder1(SWExpet)

   사용 알고리즘 :  DFS

• 기본 DFS 문제, 특이하게 테스트케이스가 개수가 아닌 번호로 들어온다. 

• 당연히 개수가 들어올줄 알고 구현했다가 로직은 분명 맞는 것 같은데 자꾸 하나만 맞길래 분노가 차올랐다. 

• 테스트케이스가 번호인 것을 알고나서 너무 허탈했다. input이 어떻게 들어오는지 꼼꼼히 확인하자는 교훈을 얻었다.......

문제에 대한 접근&생각

1. 사다리타고 내려가기 -> 3가지방향 왼쪽,오른쪽, 아래-> DFS!

다른 방법 풀이

• 전부다 하지않고 도착지점(2) 부터 시작하여 거꾸로 탐색한다. 

코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

import java.util.Scanner;   public class Solution {     static int[][] map;     static int n;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = 100;         for(int t = 1; t<=10; t++) {             sc.nextInt();             map = new int[n][n];             for(int i = 0; i < n;i++) {                 for(int j = 0; j < n; j++) {                     map[i][j] = sc.nextInt();                 }             }             int i = 0;             flag = false;             for(i = 0; i < n; i++) {                 if(map[0][i]==1) {                     visited = new boolean[n][n];                     dfs(0, i);                     if(flag) break;                 }             }                          System.out.println("#"+t+" "+i);         }     }     static int[] dx = {0,0,1};     static int[] dy = {-1,1,0};     static boolean flag;     static boolean[][] visited;     public static void dfs(int x, int y) {         if(map[x][y]== 2) {             flag = true;             return;         }         visited[x][y] = true;         for(int i = 0; i < 3; i++) {             int nx = x + dx[i];             int ny = y + dy[i];             if(isBoundry(nx, ny) &&!visited[nx][ny] &&(map[nx][ny] == 1 || map[nx][ny]==2)) {                 dfs(nx, ny);                 return;             }         }              }     private static boolean isBoundry(int nx,int ny) {         if(nx < 0|| ny < 0|| nx >=n || ny>=n) return false;         return true;     }  }   Colored by Color Scripter

cs

 

얻은 것

• 익숙함에 속지말자...