[Programmers] 배달 - Summer/Winter Coding(~2018)

// 배달 - Summer/Winter Coding(~2018) (DFS or 다익스트라)
public class Delivery {
	private static int[][] matrix; // 그래프를 저장할 배열
	private static boolean[] visit;
	private static boolean[] result; // 배달 가능한 마을을 저장할 배열

	public int solution(int N, int[][] road, int K) {
		matrix = new int[N + 1][N + 1];
		visit = new boolean[N + 1];
		result = new boolean[N + 1];
		int cnt = 0;

		for (int[] r : road) {
			matrix[r[0]][r[1]] = matrix[r[0]][r[1]] == 0 ? r[2] : Math.min(matrix[r[0]][r[1]], r[2]); // 노드 사이에 엣지가 두개 이상인 경우도 있기 때문에 가중치가 최소값인 엣지를 matrix에 저장
			matrix[r[1]][r[0]] = matrix[r[1]][r[0]] == 0 ? r[2] : Math.min(matrix[r[1]][r[0]], r[2]);
		}
		dfs(1, K, 0); // 1번 마을에서 시작
		for (boolean flag : result) {
			if (flag) cnt++;
		}
		return cnt;
	}

	private static void dfs(int s, int k, int w) {
		result[s] = visit[s] = true;
		for (int i = 1; i < matrix.length; i++) {
			if (matrix[s][i] != 0 && !visit[i] && w + matrix[s][i] <= k) { // 가중치의 합이 k를 넘지 않을 때 탐색
				dfs(i, k, w + matrix[s][i]);
			}
		}
		visit[s] = false; // 탐색이 끝나면 방문한 노드를 초기화 해줘야 함; TC2 참고
	}
}