글 읽기 - 반례좀 찾아 주세요....

fms2014 4년 전 0

반례를 구할려고 그래프를 그리고 이전 질문에서 반례를 찾아보았지만 알아낼 수 없었습니다..

혹시 반례좀 찾아주실 수 있으신가요??

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {
    static boolean flag1 = false;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]); // 정점 개수
        int M = Integer.parseInt(line[1]); // 간선 개수
        int start = Integer.parseInt(line[2]); // 시작 정점
        
        LinkedList<String>[] list = new LinkedList[N + 1]; // 그래프 구현을 위한 리스트 배열
        Stack<String> s = new Stack<>();
        Queue<String> q = new LinkedList<>();
        boolean[] flags = new boolean[N + 1]; // 방문기록을 할 배열
        
        ////////// 그래프 만들기 시작 /////////
        for (int i = 1; i <= N; i++) {
            list[i] = new LinkedList<>();
        }
        for (int i = 0; i < M; i++) {
            line = br.readLine().split(" ");
            list[Integer.parseInt(line[0])].add(line[1]);
            list[Integer.parseInt(line[1])].add(line[0]);
        }
        ////////// 그래프 만들기 끝 /////////
        
        for (int i = 1; i <= N; i++) {
            Collections.sort(list[i]); // 정점 번호가 작은 순 부터 방문하기 위한 사전 정렬
        }
        
        dfs(list, flags, start, s); // dfs시작
        for (int i = 0; i < flags.length; i++) {
            flags[i] = false; // 방문기록 초기화
        }
        bw.write("\n");
        bfs(list, flags, start, q); // bfs시작
        bw.flush();
        br.close();
        bw.close();
    }

    public static void dfs(LinkedList<String>[] list, boolean[] flags, int start, Stack<String> s) throws IOException {
        ///// 첫 시작 정점 방문 처리 시작/////
        flags[start] = true;
        s.push(String.valueOf(start));
        bw.write(start + " ");
        ///// 첫 시작 정점 방문 처리 끝/////
        
        ///// 이후 방문 처리 /////
        while (true) {
            for (int i = 0; i < list[start].size(); i++) { // 방문한 정점과 연결된 정점 탐색
                if (!flags[Integer.parseInt(list[start].get(i))]) { // 방문한 적 없는 정점이 있을 경우
                    
                    ///// 방문 처리 /////
                    start = Integer.parseInt(list[start].get(i));
                    flags[start] = true;
                    s.push(String.valueOf(start));
                    bw.write(start + " ");
                    i = -1; // for의 i를 다시 0부터 시작시키기 위한 초기화 과정
                    flag1 = false; // 백트래킹 이후에 다시 다른 정점을 방문
                    ///// 방문 처리 끝/////
                    continue;
                }
            }
            if (flag1) { // 백트래킹 후 주변 정점을 전부 탐색 했을 경우
                s.pop(); // 방문기록 삭제
            }
            if(s.isEmpty()){ // 전부 방문 했을 경우 dfs 종료
                break;
            }
            start = Integer.parseInt(s.peek()); // 마지막으로 방문한 정점 확인
            flag1 = true; // 백트래킹 확인용 플래그
        }
    }

    public static void bfs(LinkedList<String>[] list, boolean[] flags, int start, Queue<String> q) throws IOException {
        ///// 첫 시작 정점 방문 처리 시작/////
        flags[start] = true;
        q.offer(String.valueOf(start));
        ///// 첫 시작 정점 방문 처리 끝/////
        
        
        do {
            start = Integer.parseInt(q.poll()); // 먼저 정점을 방문한 기록 가져오기
            bw.write(start + " ");
            for (int i = 0; i < list[start].size(); i++) {
                if (!flags[Integer.parseInt(list[start].get(i))]) { // 방문한 적이 없을 경우
                    q.offer(list[start].get(i)); // 방문
                    flags[Integer.parseInt(list[start].get(i))] = true; // 방문 했다고 기록 남김
                }
            }
        } while (!q.isEmpty());
    }
}

djm03178 4년 전 1

간선 리스트를 String형으로 저장하고 계신데, 이 때문에 sort에 문제가 발생합니다.

String형 "10"은 "9"보다 작은 문자열입니다.

2 1
9
10

fms2014 4년 전 0

@djm03178

아.... 전혀 생각도 못했네요.

감사합니다!!

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

문제

문제

출처

ICPC

반례좀 찾아 주세요....

fms2014 4년 전 0

djm03178 4년 전 1

fms2014 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말