LEVEL 3 : 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

• 문제

  • 

    문제 

  • 

    제한 사항

  • 효율성 체크가 있는 문제이다( BFS 하기에는 시간 초과)

---

풀이

• N * M 크기의 MAP을 선언하여 웅덩이를 -1로 세팅한다( 나머지는 0) --- > 초기
• 이중 FOR문을 돈다
  • 경우 1 : 물 웅덩이일 경우 -> map[i][j]map [i][j] == -1 일 경우 map [i][j]를 0으로 세팅해 준다(물 웅덩이를 지난 경우의 수가 있을 수 없기 때문에 0개의 경우의 수다)
  • 경우 2 : 물 웅덩이가 아닐경우 -> map [i][j]가 지날 갈 수 있는 경우
    • map [i][j]를 오기 위해서는 i!= 0 , j!= 0 일 경우에는 map [i-1][j]을 경로를 거치거나, map [i][j-1] 경로를 거쳐야 된다.
    • 경우 2-1 : i != 0 이 아닐 때, map [i-1][j] 값을 map [i][j]에 더해준다.
    • 경우 2-2 : j != 0 이 아닐 때, map [i][j-1] 값을 map [i][j]에 더해준다.
• map [n-1][m-1]를 1000000007로 나눈 나머지를 리턴한다.

• public static int solution(int m, int n, int[][] puddles) {
      int[][] map = new int[n][m];
      for(int[] xy: puddles) {
        	int x = xy[0] - 1;
        	int y = xy[1] - 1;
        	map[y][x] = -1;//물 웅덩이 -1값으로 초기화
      }
      map[0][0] = 1;// 시작 경우의 수 1
      for(int i=0;i<n;++i) {
      	for(int j=0;j<m;++j) {
      		if(map[i][j] == -1) {//만약 물 웅덩이일 경우
      			map[i][j] = 0;// 물웅덩이가 map[i-1][j],map[i][j-1]일 경우 물웅덩이는 경우의 수에 포함되면 안되니까 0으로 세팅
      			continue;
      		}
      		if(i != 0 ) { // i가 0이 아닐때
      			map[i][j] += map[i - 1][j] % 1000000007; // 현재 위치에 map[i-1][j] 를 더한다
      		} 
      		if(j != 0) {
      			map[i][j] += map[i][j-1] % 1000000007; // 현재 위치에 map[i][j-1] 를 더한다
      		}
      	}	
      }
  	return map[n-1][m-1] % 1000000007;//최종까지 갔을때의 경우의 수를 리턴
  }