글 읽기 - 틀린부분을 모르겠습니다. 도움 요청합니다

quarl894 5년 전 0

bfs로 구현했고,

탐색할때, 방문확인하고 숫자가 1이상차이나는지 확인 후 다 적합하면 큐에 넣고 돌렸습니다.

또한, flag를 통해서 빠져나간게 정상적으로 빠져나간거면 출력, 아니면 -1로 출력했는데 틀린부분을 모르겠습니다.

어디가 틀렸을까요?ㅠ

package com.company;

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

public class bj_2479 {
    static int n;
    static int k;
    static String[] arr;
    static boolean[] visited;
    static int a;
    static int b;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        visited = new boolean[n+1];
        arr = new String[n+1];
        for(int i=1; i<=n; i++){
            arr[i] = br.readLine();
        }
        String[] t1 = br.readLine().split(" ");
        a = Integer.parseInt(t1[0]);
        b = Integer.parseInt(t1[1]);

        bfs(a);
        br.close();
    }

    private static void bfs(int index){
        Queue<hamming> q = new LinkedList<>();
        String result = "";
        visited[index] = true;
        boolean flag = false;
        q.offer(new hamming(index,index +""));

        // 방문한곳 제외, 차이가1인것 빼고 넣어줌. 빠져나가면 flag를 통해 -1인지 값인지 출력.
        while(!q.isEmpty()){
            hamming h = q.poll();
            int num = h.s;
            result = h.ans;
            for(int i=1; i<=n; i++){
                if(!visited[i]){
                    if(chked(num, i)){
                        result += " " +i;
                        if(b==i){
                            flag = true;
                            break;
                        }
                        q.offer(new hamming(i,result));
                        visited[i] = true;
                    }
                }
            }
        }
        if(flag) System.out.println(result);
        else System.out.println(-1);
        return;
    }

    // 다른 수가 1개인지 아닌지 판별하는 곳.
    private static boolean chked(int s, int e){
        // 1일 때
        char[] ch1 = arr[s].toCharArray();
        char[] ch2 = arr[e].toCharArray();
        int cnt = 0;

        for(int i=0; i<k; i++){
            if(ch1[i]!=ch2[i]) ++cnt;
            if(cnt>1) return false;
        }
        if(cnt==1) return true;
        else return false;
    }

    private static class hamming {
        int s;
        String ans;

        public hamming(int s, String ans) {
            this.s = s;
            this.ans = ans;
        }
    }
}

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

문제

문제

출처

ICPC

틀린부분을 모르겠습니다. 도움 요청합니다

quarl894 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말