글 읽기 - 어떤부분이 틀린건가요?

zxcv5052 3년 전 0

자료구조

- 링크드리스트로 [ROW] , <COL, 중량제한> 으로 가져갔습니다.

- 들렀던 장소를 Visit으로 1차 boolean 배열로 저장했습니다.

- Input으로 받은 <중량제한 중 가장 큰 것을 > High , <중량제한 중 가장 작은 것을 > Low로 저장했습니다.

풀이 방법

- 이분탐색과 BFS를 사용했습니다.

- 먼저 범위는 받았던 High와 Low를 기준으로 잡았습니다.

- 이분탐색을 쓰면서 mid의 값일 때 BFS로 통과하는지 확인하고

- IF) BFS 통과 X _ 현재 중량으로는 통과하지 못하므로 중량의 크기를 줄이기 위해 High = mid-1을 해주었습니다.

- IF) BFS 통과 O _ 현재 중량으로는 통과하므로 답이 될 수 있다 생각하고 result = mid && low = mid+1 을 해주었습니다.

틀린이유가뭔가요?

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

public class BaekJoon2206 {
    static int N;
    static int M;
    static ArrayList<Location>[] map ;
    static boolean[] visit; // from
    static int endLoc;
    static int high = 1;
    static int low = Integer.MAX_VALUE  ;
    static Queue<Integer> queue; // from
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new ArrayList[N+1];
        for(int i=1; i<N+1; i++){
            map[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int limit = Integer.parseInt(st.nextToken());
            high = Math.max(high, limit);
            low = Math.min(low, limit);
            map[a].add(new Location(b,limit));
            map[b].add(new Location(a,limit));
        }

        st = new StringTokenizer(br.readLine());
        int startLoc = Integer.parseInt(st.nextToken());
        endLoc = Integer.parseInt(st.nextToken());
        br.close();

        int result = 0;

        while(high>= low){
            queue = new LinkedList<>();
            queue.add(startLoc);
            visit = new boolean[N+1];
            int mid = (high+low)/2;
            visit[startLoc] = true;
            if( bfs(mid) ) {
                result = mid;
                low = mid+1;
            }
            else{
                high = mid-1;
            }
        }
        System.out.println(result);
    }

    static boolean bfs(int weight){
        while(!queue.isEmpty() ){
            int nowLoc = queue.poll();
            if(nowLoc == endLoc){
                return true;
            }
            for(int i=0; i < map[nowLoc].size(); i++){
                int to = map[nowLoc].get(i).to;
//                System.out.print(" can go :" + to);
                int limit = map[nowLoc].get(i).limit ;
//                System.out.println(" limit : " + limit);
                if( !visit[to] && weight <= limit){
                    queue.add(to);
                    visit[to] = true;
                }
            }
        }
        return false;
    }
}
class Location{
    int to;
    int limit;

    public Location(int to, int limit) {
        this.to = to;
        this.limit = limit;
    }
}

zxcv5052 3년 전 0

죄송합니다. 뭔가 착오가 있었어요ㅠ

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

문제

문제

출처

ICPC

어떤부분이 틀린건가요?

zxcv5052 3년 전 0

zxcv5052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말