글 읽기 - 90% 실패ㅠㅠ

gisung2215 2년 전 0

90%에서 실패하네요. 조언 부탁드립니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static boolean flag;
    static int N, M;
    static int[][] map;
    static int[] sel;
    static Flog[] flogs;

    public static void main(String[] args) throws Exception {
        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 int[N + 1][N + 1];
        flogs = new Flog[N + 1];
        sel = new int[N + 1];

        // 각 개구리 관심분야 설정
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int food = Integer.parseInt(st.nextToken());
            int hobby = Integer.parseInt(st.nextToken());
            int family = Integer.parseInt(st.nextToken());
            int study = Integer.parseInt(st.nextToken());
            flogs[i] = new Flog(food, hobby, family, study);
        }

        int remain = N;
        // 선호지역 입력
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            flogs[i].setFRegion(a, b); 
            if (a == b) { // 개구리의 선호지역 2개가 동일하다면 고정
                sel[a] = i;
                remain--;
            }
        }

        // 통나무 대화 주제 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            map[from][to] = val;
            map[to][from] = val;
        }

        flag = false;
        perm(1, remain); // 1번 개구리부터, 남은 연꽃 갯수
        if (!flag) System.out.println("NO");

    }

    private static void perm(int start, int remain) {
        if(flag) return;
        if(remain == 0){
            // 연꽃 배정이 끝났다면, 통나무의 대화 주제 조건과 일치하는지 비교
            for(int i=1; i<N; i++){
                for(int j=i+1; j<N+1; j++){
                    if(map[i][j] == 0) continue;
                    int type = map[i][j];
                    if(flogs[sel[i]].interests[type] != flogs[sel[j]].interests[type]) return;
                }
            }
            
            // 모든 조건을 만족한다면 출력
            flag = true;
            System.out.println("YES");
            for(int i=1; i<=N; i++){
                System.out.print(sel[i] + " ");
            }
        }else{
            if(start > N) return;
            int a = flogs[start].FRegion1; // 개구리의 첫번째 선호 지역
            int b = flogs[start].FRegion2; // 개구리의 두번재 선호 지역

            if (a == b) perm(start + 1, remain); // 선호지역 2개가 일치한다면, 이미 배정 완료
            else {
                if (sel[a] == 0) { // 선호 지역이 비어있다면 배정
                    sel[a] = start;
                    perm(start + 1, remain - 1); // 개구리 번호 증가, 남은 연꽃 갯수 감소
                    sel[a] = 0;
                }
                if (sel[b] == 0) {
                    sel[b] = start;
                    perm(start + 1, remain - 1);
                    sel[b] = 0;
                }
            }
        }
    }

    public static class Flog {
        int interests[] = new int[5]; // 관심 분야 4가지
        int FRegion1, FRegion2; // 선호 지역 1, 2

        public Flog(int food, int hobby, int family, int study) {
            this.interests[1] = food;
            this.interests[2] = hobby;
            this.interests[3] = family;
            this.interests[4] = study;
        }

        public void setFRegion(int a, int b) {
            this.FRegion1 = a;
            this.FRegion2 = b;
        }
    }
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

90% 실패ㅠㅠ

gisung2215 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
