[Baekjoon] 4883_삼각 그래프

Silver I

문제(출처: https://www.acmicpc.net/problem/4883)

---

< 삼각 그래프 >

 

문제 풀이 

 

처음에는 가장 위쪽 가운데 정점에서부터 시작해서 Queue를 사용해서 이동하는 곳마다 저장하여 최소 비용을 구하도록 구현했다. 하지만 중복되는 위치가 있어서 그런지 시간초과가 발생했다.

 

삼각 그래프 각 정점에서 이동할 수 있는 위치는 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래 총 4가지 경우이다. 그러므로 정점을 위에서부터, 왼쪽에서 오른쪽으로 탐색해도 된다는 뜻이다. 왼쪽으로 이동할 수 없고, 위로 이동할 수 없기 때문이다. 또한, 비용의 제곱이 1,000,000이므로 비용이 음수일 수 도 있다는 뜻이므로 최소 비용을 구하는 배열의 초기값을 0으로 설정하면 정확한 답을 구할 수 없으므로 Integer.MAX_VALUE를 사용하여 초기화했다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _4883_ { // 삼각 그래프
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

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

		int arr[][], result[][];
		int n = 0;
		int idx = 1;

		while ((n = Integer.parseInt(bf.readLine())) != 0) {
			arr = new int[n][3];
			result = new int[n][3];

			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(bf.readLine());
				for (int j = 0; j < 3; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
					result[i][j]=Integer.MAX_VALUE;
				}
			}

			result[0][1] = arr[0][1];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < 3; j++) {
					if (result[i][j] != Integer.MAX_VALUE) {
						for (int k = 0; k < 4; k++) {
							int x = i + dx[k];
							int y = j + dy[k];
							if (x >= 0 && x < n && y >= 0 && y < 3) {
								if (result[x][y] == Integer.MAX_VALUE || (result[x][y] > result[i][j] + arr[x][y])) {
									result[x][y] = result[i][j] + arr[x][y];
								}
							}
						}
					}
				}
			}
			bw.write(idx++ + ". " + result[n - 1][1] + "\n");
		}
		bw.flush();
	}
}

변수)
dx, dy : 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래
arr : 정점의 비용
result : 최소 비용
n : 그래프 행의 개수
idx : 테스트 케이스 번호

 

정점의 비용을 입력받으면서 최소 비용을 구하는 배열을 Ineger.MAX_VALUE로 초기화한다. 가장 위쪽 가운데부터 시작하므로 가장 위쪽 가운데 값을 최소 비용을 구하는 배열(result)에 저장한다. 그 후 result 배열을 전체 탐색하면서 값이 Integer.MAX_VALUE가 아닌 위치를 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래로 이동하여 최솟값인지 확인 후 값을 바꾼다.

 

최종 테스트 케이스 번호와 가장 아래쪽 가운데 정점의 값을 출력한다.

---

---