백준 23352번: 방탈출

문제 설명

• https://www.acmicpc.net/problem/23352
• 가장 긴 통로를 구하는 문제입니다. 단, 통로의 길이가 같으면 시작지점 + 도착지점의 값이 더 큰 경우를 선택합니다.

접근법

• BFS로 길이를 구합니다.
• 각 너비별로 가장 큰 숫자를 구해야 합니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		int[] result = new int[] { 0, 0 };
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0)
					continue;
				int[] temp = BFS(new int[] { i, j }, board);
				if (result[0] < temp[0]) {
					result = temp;
				} else if (result[0] == temp[0] && result[1] < temp[1]) {
					result = temp;
				}
			}
		}
		System.out.println(result[1]);
	}

	public static int[] BFS(int[] start, int[][] board) {
		Queue<int[]> q = new LinkedList<int[]>();
		boolean[][] v = new boolean[N][M];
		v[start[0]][start[1]] = true;
		q.add(start);
		int cnt = 0;
		int maxVal;
		while (!q.isEmpty()) {
			maxVal = Integer.MIN_VALUE; // 이번 너비에서 가장 큰 숫자를 담습니다.
			cnt++;
			int size = q.size();
			while (--size >= 0) {
				int[] now = q.poll();
				maxVal = board[now[0]][now[1]];
				for (int d = 0; d < 4; d++) {
					int nx = now[0] + dx[d];
					int ny = now[1] + dy[d];
					if (0 <= nx && nx < N && 0 <= ny && ny < M && !v[nx][ny] && board[nx][ny] != 0) {
						v[nx][ny] = true;
						q.add(new int[] { nx, ny });
						maxVal = Math.max(maxVal, board[nx][ny]); // 이번 너비에서 가장 큰 숫자를 갱신합니다.
					}
				}
			}
		}
        // {경로의 길이,시작위치+도착위치의 값}를 반환합니다.
		return new int[] { cnt, maxVal + board[start[0]][start[1]] };
	}
}