문제 :
https://www.acmicpc.net/problem/1103
접근 :
- 현재까지의 도달한 값을 dp 에 저장
- 4방향으로 탐색을 실행 후, 만약 다음값이 dp 보다 크다면 더이상 탐색을 진행하지 않는다.
> 이미 다른 경로를 통하여 해당 위치에 왔을때, 이전에 지나온 길이가 긴 것의 결과가 무조건 큰 수가 나오기 때문
> ex) before + after = res 라고 할때 before 가 큰 res가 무조건 더 크기 때문 (after 는 같은 값)
- 만약 다음 값이 H인 경우에도 더이상 탐색을 진행하지 않는다.
- 방문한 노드를 다시 방문한 경우에는 cyle이 생성되서 무한이므로 -1을 리턴한다.
코드 구현 :
import java.io.*;
public class Main {
private static int[][] map;
private static int[][] dp;
private static boolean[][] visited;
private static Position[] dir;
private static int res;
private static class Position{
private final int x;
private final int y;
public Position(int x, int y){
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
private static void dfs(Position now, int count){
int val = map[now.getX()][now.getY()];
int nx, ny;
if(res == -1) return;
dp[now.getX()][now.getY()] = count;
res = Math.max(res, count);
for(Position d : dir){
nx = now.getX() + val*d.getX();
ny = now.getY() + val*d.getY();
if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length) continue;
if(visited[nx][ny]) {
res = -1;
return ;
}
if(map[nx][ny] == -1) continue;
if(dp[nx][ny] > count) continue;
visited[nx][ny] = true;
dfs(new Position(nx, ny), count+1);
visited[nx][ny] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
dir = new Position[]{
new Position(0,1), new Position(1,0), new Position(0,-1), new Position(-1,0)
};
dp = new int[n][m];
map = new int[n][m];
visited = new boolean[n][m];
res = 0;
String temp;
for(int i = 0 ; i < n ; i++){
temp = br.readLine();
for(int j = 0 ; j < m ; j++){
map[i][j] = (temp.charAt(j) == 'H') ? -1 : (temp.charAt(j) - '0');
}
}
dfs(new Position(0,0),1);
System.out.println(res);
br.close();
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 숫자 변환하기_DP (1) | 2024.07.12 |
---|---|
[JAVA] 프로그래머스 주차 요금 계산_tree map (0) | 2024.07.10 |
[JAVA] 백준 1913 달팽이_탐색 (0) | 2024.07.05 |
[JAVA] 프로그래머스 타겟 넘버_탐색 (0) | 2024.07.04 |
[JAVA] 프로그래머스 피로도_브루트포스 (0) | 2024.07.04 |