글 읽기 - TC, 반례 모두 맞는데 왜 틀렸는지 모르겠네요 ㅠㅠ

l9960204 4년 전 0

반례 또는 틀린곳을 찾아주신다면 감사하겠습니다. ㅠㅠ

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[] di = { 0, 1, 0, -1 };
	static int[] dj = { 1, 0, -1, 0 };
	static int N, M;
	static int[][] num;
	static boolean[][] visited;
	static int[][] open;
	static Queue<Point> queue;

	static boolean check(int i, int j) {
		if (i >= 0 && i < N && j >= 0 && j < M)
			return true;
		else
			return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		num = new int[N][M];
		open = new int[N][M];
		visited = new boolean[N][M];

		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				num[i][j] = sc.nextInt();
				max = num[i][j] > max ? num[i][j] : max;
			}
		}
		int max_num = max;
		queue = new LinkedList<>();
		int cnt = 4;
		while (cnt > 0) {
			boolean flag = true;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (max == num[i][j]) {
						open[i][j] = num[i][j];
						queue.add(new Point(i, j));
					}
					
					if(open[i][j] == 0 && flag)
						flag = false;
				}
			} // 일단 가장 큰 값을 가진 곳만 열어준다
			
			if(flag)
				break;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {
					Point now = queue.poll();
					visited[now.i][now.j] = true;
					for (int d = 0; d < 4; d++) {
						int ni = now.i + di[d];
						int nj = now.j + dj[d];

						if (check(ni, nj) && !visited[ni][nj] && num[ni][nj] >= max) {
							queue.add(new Point(ni, nj));
							open[ni][nj] = num[ni][nj];
						}
					}
				}
				cnt--;
			} // enw queue while
			max--;
		}
		
		for (int i = 0; i < N; i++) {
			Arrays.fill(visited[i], false);
		}
		queue.clear();
//		print();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(open[i][j] != 0 && !visited[i][j]) {
					visited[i][j] = true;
					dfs(i, j, 1, open[i][j]);
					for (int k = 0; k < N; k++) {
						Arrays.fill(visited[k], false);
					}
				}
			}
		}
		
		System.out.println(max_result);
	}
	
	static int max_result = 0;
	static void dfs(int i, int j, int cnt, int sum) {
		visited[i][j] = true;
//		System.out.println(sum);
		if(cnt == 4) {
			max_result = sum > max_result ? sum : max_result;
			return;
		}
		
		if(cnt == 2) {
			int tmp = sum;
			if(check(i-1, j) && !visited[i-1][j] && check(i+1, j) && !visited[i+1][j]) {
				tmp += open[i-1][j];
				tmp += open[i+1][j];
				max_result = tmp > max_result ? tmp : max_result;
			}
			
			tmp = sum;
			if(check(i, j-1) && !visited[i][j-1] && check(i, j+1) && !visited[i][j+1]) {
				tmp += open[i][j-1];
				tmp += open[i][j+1];
				max_result = tmp > max_result ? tmp : max_result;
			}
		}
		
		for (int d = 0; d < 4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];

			if (check(ni, nj) && !visited[ni][nj] && open[ni][nj] != 0) {
				visited[ni][nj] = true; //
				dfs(ni, nj, cnt+1, sum+open[ni][nj]);
				visited[ni][nj] = false; //
			}
		}
	}

	static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(open[i][j] + " ");
			}
			System.out.println();
		}
	}

	static class Point {
		int i, j;

		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}

		@Override
		public String toString() {
			return "Point [i=" + i + ", j=" + j + "]";
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

TC, 반례 모두 맞는데 왜 틀렸는지 모르겠네요 ㅠㅠ

l9960204 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말