Q1520. 내리막길

토요일날 공부하기 힘드네요

플루이드 로직을 활용하여, 경로 개수를 찾는 로직입니다.

map[y][x] = 1로 설정후 mapSearch(1,1) 플루이드 로직을 통해, 경로 찾습니다.

시간 초과가 발생하기 때문에, isVisit 플래그를 추가하여, 한번 탐색한 경로일 경우

재 탐색을 하지 말고 경로를 return 합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1520 { static long[][][] map; static int y, x; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); y = Integer.parseInt(st.nextToken()); x = Integer.parseInt(st.nextToken()); map = new long[2][y+1][x+1]; for (int i = 1; i <= y; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= x; j++) { map[0][i][j] = Integer.parseInt(st.nextToken()); map[1][i][j] = -1; } } map[1][y][x] = 1; System.out.println(searchValue(1, 1)); } public static long searchValue(int nowY, int nowX) { //상, 하 , 좌, 우 if (map[1][nowY][nowX] != -1) { return map[1][nowY][nowX]; } map[1][nowY][nowX] = 0; if (1 < nowY) { if (map[0][nowY][nowX] > map[0][nowY-1][nowX]) { map[1][nowY][nowX] += searchValue(nowY-1, nowX); } } if (nowY < y) { if (map[0][nowY][nowX] > map[0][nowY+1][nowX]) { map[1][nowY][nowX] += searchValue(nowY+1, nowX); } } if (1 < nowX) { if (map[0][nowY][nowX] > map[0][nowY][nowX-1]) { map[1][nowY][nowX] += searchValue(nowY, nowX-1); } } if (nowX < x) { if (map[0][nowY][nowX] > map[0][nowY][nowX+1]) { map[1][nowY][nowX] += searchValue(nowY, nowX+1); } } return map[1][nowY][nowX]; } }