[백준] 4883번 : 삼각 그래프

문제

 

 

접근 방식

풀고 나서도 이게 그래프인지 DP 풀이인지 모르겠는 문제였다.

 

 

우선 그래프의 한 정점을 기준으로 위와 같이 이동할 수 있으며

2차원 배열을 처음부터 끝까지 돌면서 위와 같이 이동만 해주며 DP 테이블을 채워주면 된다.

 

따로 방문여부를 기록하지 않고 DP 테이블의 값이 0인지 아닌지로

확인하려 했는데 정점의 값이 음수인 경우도 있어서 합이 0일 때가 있을 수 있기 때문에

따로 방문 여부를 기록할 불리언 배열을 사용했다.

 

각 정점(i, j)에서 갈 수 있는 정점들을 방문하며

처음 방문한 정점(x, y)이면 방문 여부를 참으로 바꾸고,

(x, y)의 DP 테이블에 (i, j) 테이블의 값 + 현재 정점의 값을 기록하고

이미 방문한 정점이라면 이미 기록된 값과 새로운 값 중 더 작은 값을 기록한다.

 

목적지까지 테이블을 다 채운 후에 목적지의 값을 출력해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int[] dx = {0, 1, 1, 1};
		int[] dy = {1, -1, 0, 1};
		int tc = 1;

		while (true) {
			int n = Integer.parseInt(br.readLine());

			if (n == 0) break;

			int[][] arr = new int[n][3];
			int[][] dp = new int[n][3];
			boolean[][] isVisited = new boolean[n][3];

			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());

				for (int j = 0; j < 3; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][1] = arr[0][1];
			isVisited[0][1] = true;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < 3; j++) {
					if (i == 0 && j == 0) continue;
					if (i == n - 1 && j == 1) {
						sb.append(tc++).append(". ").append(dp[i][j]).append("\n");
						break;
					}

					for (int dir = 0; dir < 4; dir++) {
						int x = i + dx[dir];
						int y = j + dy[dir];

						if (y < 0 || x >= n || y >= 3) continue;

						if (isVisited[x][y]) {
							dp[x][y] = Math.min(dp[x][y], dp[i][j] + arr[x][y]);
						} else {
							isVisited[x][y] = true;
							dp[x][y] = dp[i][j] + arr[x][y];
						}
					}
				}
			}
		}

		System.out.println(sb);
	}
}