글 읽기 - BFS만 이용해서 풀어봤는데 BFS만 이용할 경우 틀렸다고 나오나요?

pl10hg 4년 전 0

BFS만 이용해서 풀어봤는데요

예제는 맞지만 이후 채점에서 틀렸다고 나오네요

BFS 방식으로만 풀었을 경우에는 오답으로 나오나요?

틀린 부분이 있다면 힌트주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

    public static void main(String[] agrs) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] map = new int[n][n];
        check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = 0;

        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 1;
                q.add(i);
                q.add(j);
                q.add(temp);
                check[i][j] = true;

                while (!q.isEmpty()) {
                    int x = q.poll();
                    int y = q.poll();
                    temp = q.poll();
                    if (ans < temp) ans = temp;
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                        if (map[x][y] < map[nx][ny] && check[nx][ny] == false) {
                            q.add(nx);
                            q.add(ny);
                            q.add(temp + 1);
                            check[nx][ny] = true;
                        }
                    }
                }
                check(n);
            }
        }

        System.out.println(ans);
    }

    private static void check(int n) {

        for(int i=0; i<n; i++){
            Arrays.fill(check[i], false);
        }
    }
}

lim551 4년 전 2

최장거리를 구해야하기 때문에 방문했던 곳을 또 방문해야할지 모릅니다.

예를 들어 2-1을 먼저 방문해서 1에서의 최장거리를 2라고 계산한 상태에서 4-3-1이라는 경로가 있을 경우 1에서의 최장거리가 3이라고 판단하지 못합니다.

dfs와 dp를 통해 답을 구하거나 말단 노드부터 역으로 계산하시는걸 추천합니다.

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

문제

문제

출처

ICPC

BFS만 이용해서 풀어봤는데 BFS만 이용할 경우 틀렸다고 나오나요?

pl10hg 4년 전 0

lim551 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말