글 읽기 - 20% 좀 넘어가다가 틀린것으로 나오는데, 왜 그런지는 잘 모르겠습니다...

kimjh9434 5년 전 0

음냐... 지금까지 그냥그냥 막혀도 질문 게시판을 읽어나가면서 어떻게든 풀어나갔는데,

이번에는 어떻게 접근해야할지 몰라서 처음으로 질문을 남겨봅니다.

일단, https://www.acmicpc.net/board/ 에서 언급하고 있는 예제는 모두 통과했고,

그 밖의 게시판의 질문들에서 예시로 드는 것들도 모두 통과했다고 생각합니다.

[다른 질문들의 문제점으로 ' 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문' 도 만족한다고 생각합니다]

[참고로 작업환경은 이클립스입니다]

기본적으로 그래프 문제라고 생각해서,

좀 복잡하게 생각한 걸수도 있지만 간단하게 Graph, Point 클래스를 만들었고,

DFS용인 PointArrayStack 클래스와 BFS용인 PointArrayQueue 클래스도 만들어서 이용해보았습니다.

[이전 단계 문제에서 이미 스택, 큐 클래스를 만들어놓은게 있어서, 기본 자료형만 바꿨습니다]

기본적인 단계로는,

1. N, M, V를 입력받고,

2. N개의 점점으로 이루어진 그래프를 만들고,

3. 그래프의 인접행렬을 오름차순으로 정렬한 뒤에,

4. DFS 알고리즘 수행,

5. BFS 알고리즘 수행으로 이루어집니다.

확실히 코드 자체가 비효율적일지도 모르겠지만,

일단 맨 처음에 생각했던 방향대로 밀고 나가다보니 저런 코드가 탄생했습니다.

그리고 일단 전체 뼈대를 세운 뒤에, 각종 예제들을 테스트하면서 발견하게 된 문제들을 해결하다보니

코드가 좀 더 지저분해진 감이 있습니다만, 일단 제가 아는 선 내에서는 문제를 해결했다고 생각하지만,

실질적으로 문제를 제출하면 20%좀 뜨는 순간 바로 틀렸다고 나와버립니다.

어디가 문제인지 안다면 해결을 시도할 수도 있을텐데, 도저히 감이 안와서 이렇게 질문을 올려봅니다.

CF. 추가적으로 시도해본 예제

15 14 15

1 2

1 3

2 4

2 5

3 6

3 7

4 8

4 9

5 10

5 11

6 12

6 13

7 14

7 15

입력시 =>

15 7 3 1 2 4 8 9 5 10 11 6 12 13 14

15 7 3 14 1 6 2 12 13 4 5 8 9 10 11

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// Q2 1260 DFS와 BFS

		// 2018-08-02-목. 4차 시도

		// 간단한 문제 정리
		// 일단은... 기본적으로 그래프 문제로 보인다.
		// 입력된 결과를 바탕으로 N개의 그래프 및 M개의 간선을 연결한 그래프를 얻고,
		// 주어진 정점으로부터, DFS 및 BFS 알고리즘을 수행해야 한다.
		
		// 여기서 DFS 알고리즘은 스택이 필요하며, BFS 알고리즘은 큐가 필요하다.
		
		// 필요한 단계들
		// 1. 정점의 개수 N,  간선의 개수 M, 탐색을 시작할 정점의 번호 V를 입력받는다.
		
		// 2. N개의 점점으로 이루어진 그래프를 만든다.
		//  2.1. M번 반복한다.
		//   2.1.1. 두 정점의 위치를 입력받는다.
		//   2.1.2. 그래프 내에서 두 정점을 연결한다. [양쪽 모두 연결해야 함]
		
		// 3. 그래프 내의 각 정점에 대해서, 인접한 정점들을 정렬한다.
		
		// 4. DFS 알고리즘을 수행한다.
		//  4.1. 주어진 정점의 번호로부터 시작한다.
		//  4.2. i가 N에 도달하던지, 현재 위치가 null이 아닌동안 반복한다. 
		//   4.2.1. 현재 위치를 방문하지 않았다면,
		//    4.2.1.1. 현재 위치를 방문했다고 표시한다.
		//    4.2.1.2. 현재 위치를 출력한다.
		//   4.2.2. 현재 위치와 인접해 있는 정점 중 아직 안간 곳이 있다면,
		//    4.2.1.1. 현재 위치를 스택에 넣는다.
		//    4.2.1.2. 현재 위치와 인접해 있는 정점 중 가장 작은 정점으로 이동한다.
		//   4.2.3. 없다면, [= 모두 가 보았다면]
		//    4.2.3.1. 스택으로부터 가장 최근 위치를 꺼내서 현재위치로 잡는다.
		
		// 5. BFS 알고리즘을 수행한다.
		//  5.1. 주어진 정점의 번호로부터 시작한다.
		//  5.2. i가 N에 도달하던지, 현재 위치가 null이 아닌동안 반복한다. 
		//   5.2.1. 현재 위치로부터 아직 안 간 정점들을 모두 큐에 넣는다.
		//   5.2.2. 현재 위치를 방문했다고 표시한다.
		//   5.2.3. 현재 위치를 출력한다.
		//   5.2.4. 큐에서 위치를 꺼내서 현재위치로 잡는다.
		
		
		// 다양한 방법으로 스택을 구현할 수 있지만, 맨 처음이므로, 그냥 젤 단순하게 배열록 구현해보겠다.

		Scanner scan = new Scanner(System.in);
		int N, M, V;
		Graph g;
		PointArrayStack s;
		PointArrayQueue q;
		int i,j;
		int point1, point2;
		Point currentP, tempP;
		boolean isExist;
		
		// 1. 정점의 개수 N,  간선의 개수 M, 탐색을 시작할 정점의 번호 V를 입력받는다.
		N = scan.nextInt();
		M = scan.nextInt();
		V = scan.nextInt()-1;
		
		
		// 2. N개의 점점으로 이루어진 그래프를 만든다.
		g = new Graph(N);
		s = new PointArrayStack(N);
		q = new PointArrayQueue(N);
		
		//  2.1. M번 반복한다.
		for(i=0;i<M;i++){
			//   2.1.1. 두 정점의 위치를 입력받는다.
			point1 = scan.nextInt()-1;
			point2 = scan.nextInt()-1;
			
			//   2.1.2. 그래프 내에서 두 정점을 연결한다. [양쪽 모두 연결해야 함]
			g.points[point1].insert_edge(g.points[point2]);
			g.points[point2].insert_edge(g.points[point1]);
		}
		
					
		// 3. 그래프 내의 각 정점에 대해서, 인접한 정점들을 정렬한다.
		AscendingPoint ascending = new AscendingPoint();
		for(i=0;i<N;i++){
			Collections.sort(g.points[i].getAdjacency(), ascending);
		}
		
		
		// 4. DFS 알고리즘을 수행한다.
		//  4.1. 주어진 정점의 번호로부터 시작한다.
		currentP = g.points[V];
		
		//  4.2. i가 N에 도달하던지, 현재 위치가 null이 아닌동안 반복한다. 
		i=0;
		while(i<N){
			//   4.2.1. 현재 위치를 방문하지 않았다면,
			if(!currentP.isVisit()){
				//    4.2.1.1. 현재 위치를 방문했다고 표시한다.
				currentP.visit();
				
				//    4.2.1.2. 현재 위치를 출력한다.
				System.out.print(currentP.getNum()+" ");
				
				i++;
			}
			
			//   4.2.2. 현재 위치와 인접해 있는 정점 중 아직 안간 곳이 있다면,
			isExist = false;
			for(j =0;j<currentP.getAdjacency().size();j++){
				tempP = currentP.getAdjacency().get(j);
				
				if(!tempP.isVisit()){
					//    4.2.1.1. 현재 위치를 스택에 넣는다.
					s.push(currentP);
					
					//    4.2.1.2. 현재 위치와 인접해 있는 정점 중 가장 작은 정점으로 이동한다.
					currentP = tempP;
					
					isExist = true;
					
					break;
				}
			}
			//   4.2.3. 없다면, [= 모두 가 보았다면]
			if(!isExist)
			{
				//    4.2.3.1. 스택으로부터 가장 최근 위치를 꺼내서 현재위치로 잡는다.
				currentP = s.pop();
				
				if(currentP == null) break;
			}
		}
		
		System.out.println();// 줄 바꾸기 및 그래프 방문여부 초기화
		g.vistReset();
		
		// 5. BFS 알고리즘을 수행한다.
		//  5.1. 주어진 정점의 번호로부터 시작한다.
		currentP = g.points[V];
		
		//  5.2. i가 N에 도달하던지, 현재 위치가 null이 아닌동안 반복한다. 
		i=0;
		while(i<N){
			//   5.2.1. 현재 위치로부터 아직 안 간 정점들을 모두 큐에 넣는다.
			for(j = 0;j<currentP.getAdjacency().size();j++){
				tempP = currentP.getAdjacency().get(j);
				if(!tempP.isVisit()){
					q.enqueue(tempP);
				}
			}
			
			if(!currentP.isVisit()){
				//   5.2.2. 현재 위치를 방문했다고 표시한다.
				currentP.visit();
				
				//   5.2.3. 현재 위치를 출력한다.
				System.out.print(currentP.getNum()+" ");
				
				i++;
			}
			
			//   5.2.4. 큐에서 위치를 꺼내서 현재위치로 잡는다.
			currentP = q.dequeue();
			
			if(currentP == null) break;
		}
	}
}

// 오름차순 정렬
class AscendingPoint implements Comparator<Point> {
	@Override
	public int compare(Point p1, Point p2) {
		return (p1.compareTo(p2));
	}
}

// 그래프 클래스
class Graph{
	Point[] points; // 그래프내에 있는 전체 정점들의 배열
	
	Graph(int capacity){// 생성자
		points = new Point[capacity];
		
		for(int i=0;i<points.length;i++){
			points[i] = new Point(i+1);
		}
	}
	
	void vistReset(){// 방문 여부 초기화
		for(int i=0;i<points.length;i++){
			points[i].setIsVist(false);
		}
	}
}

// 정점 클래스
class Point implements Comparable<Point>{
	private int num; // 해당 정점의 숫자
	private boolean isVisit; // 방문 여부
	private ArrayList<Point> adjacency;// = new Graph[1000]; // 인접해 있는 그래프들의 배열
	
	Point(int num){// 생성자
		this.num = num;
		isVisit = false;
		adjacency = new ArrayList<Point>();
	}
	
	void insert_edge(Point g){
		this.adjacency.add(g);
	}
	void visit(){
		isVisit = true;
	}
	boolean isVisit(){
		return isVisit;
	}
	int getNum(){
		return num;
	}
	ArrayList<Point> getAdjacency(){
		return adjacency;
	}
	
	void setIsVist(boolean isVisit){
		this.isVisit = isVisit;
	}

	@Override
	public int compareTo(Point p2) {
		
		int ret = 0;
		if(num < p2.num) ret = -1;
		else if(num > p2.num) ret = 1;
		
		// 디버깅용 코드
		// System.out.println(num +","+p2.num +","+ret);
		return ret;
	}
}

//DFS용 스택
class PointArrayStack {
	private Point[] stack;
	private int top;
	
	PointArrayStack(int capacity){// 생성자
		stack = new Point[capacity];
		top = -1;
	}

	public void push(Point p) {
		stack[++top] = p;
	}

	public Point pop() {
		Point ret;
		if (!this.empty()) { // top != -1
			ret = stack[top--];
		} else {
			ret = null;
		}
		return ret;
	}

	public boolean empty() {
		return (top == -1);
	}
}

// BFS용 큐
class PointArrayQueue {
	private Point[] queue;
	private int front; // front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
	private int rear; 

	// enqueue : 정수 num을 큐에 넣는 연산이다.
	
	PointArrayQueue(int capacity){
		queue = new Point[capacity+1];
		front = 0;
		rear = 0;
	}
	
	public void enqueue(Point p) {
		if(!this.isFull() ){
			rear = (rear+1) % queue.length;
			queue[rear] = p;
		}else{
//			System.out.println("큐가 포화상태입니다");
		}
	}

	// dequeue : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
	public Point dequeue() {
		Point ret;
		if (!isEmpty()) { 
			front = (front+1) % queue.length;
			ret = queue[front];
		} else {
//			System.out.println("큐가 공백상태입니다");
			ret = null;
		}
		return ret;
	}

	public boolean isEmpty() {
		return (front == rear);
	}
	
	public boolean isFull() {
		return ((rear+1)%queue.length == front);
	}
}

djm03178 5년 전 2

코드가 너무 길어서 분석해드리긴 어렵고, 대신에 반례를 찾아 드렸습니다.

웬만큼 작은 케이스로는 거의 틀린 답이 안 나오네요.

32 1
10
7
1
5
11
1
11
5
3
9
8
5
7
4
3
12
11
13
4
11
10
2
3
1
2
11
10
7
4
9
13
5
output:
5 2 10 3 4 6 8 11 7 9 12 13 
5 6 7 2 8 9 10 4 11 3 12 13 
correct answer:
5 2 10 3 4 6 8 11 7 9 12 13 
5 6 7 2 8 9 10 4 11 3 13 12 

23 10
11
4
2
9
8
2
8
10
3
7
10
10
5
5
7
6
3
7
6
4
11
2
1
output:
2 3 1 7 4 8 11 6 5 9 
2 4 6 7 9 3 8 5 1 11 
correct answer:
2 3 1 7 4 8 11 6 5 9 
2 4 6 7 9 3 8 5 11 1 

27 3
5
1
11
7
11
3
1
6
8
2
3
13
1
2
6
8
9
13
5
7
3
4
2
6
6
9
4
output:
1 2 6 8 5 4 13 7 9 11 10 12 
1 2 7 11 4 9 13 6 12 8 5 10 
correct answer:
1 2 6 8 5 4 13 7 9 11 10 12 
1 2 7 11 4 9 13 6 12 8 10 5 

kimjh9434 5년 전 1

오오오오!!!

사실상 반례를 못찾은 상황에서 어디가 문제인지 몰라서 방치하고 있었는데, 정말로 문제가 있더군요. [역시 컴퓨터는 잘못이 없는...]

일단 반례상으로도, DFS는 잘 돌아갔는데, BFS의 맨 마지막 2개의 순서가 잘못되었던 것으로 보여서,

예시 중 하나를 일일히 그려서 손 디버깅을 하던 와중에, 문제점을 찾아냈습니다.

정점이 이미 큐에 들어가 있는데, 다른 정점입장에서는 아직 방문되어있지 않나고 나와있어서 또 넣는 문제점이 보였고

아마 그거 때문에 문제가 발생하지 않았나 추측됩니다. [반복해서 넣다보니 큐의 크기인 N을 초과하는 입력이 있을 수도 있었고, 그러다보니 정확한 타이밍에 큐 삽입이 되지 않았다던지 등의 문제가 발생해서 순서가 뒤밖이지 않았나 생각됩니다. 완전히 다 전개하지는 않아서, 완전 정확한 원인까지는 잘 모르겠내요]

[사실 따지고 보면, 이 문제 자체는 전에도 어느정도 인식하고 있긴 했는데, 적어도 주어졌던 예제상으로는 잘만 돌아갔기 때문에, 큰 문제라고 생각하지 않았던 것 같기도 합니다]

DFS는 그대로 냅두었고, BFS부분만 수정하였는데,

DFS인 스택과는 다르게, BFS인 큐는 그냥 넣는 순서 그대로 출력하기만 하면 되는 거기 때문에,

기존의 일단 큐에 넣고 뺀 이후에 방문했다고 표시하고 출력하는 방식에서

그냥 큐에 넣기 전에 미리 방문했다고 표시하고 출력도 해버린 이후에 큐에 넣는 방식으로,

큐에 중복 삽입 방지를 구현하면서 해결했는데, 제출해보니 정답이라고 나왔습니다!

감사합니다!!!

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

문제

문제

출처

ICPC

20% 좀 넘어가다가 틀린것으로 나오는데, 왜 그런지는 잘 모르겠습니다...

kimjh9434 5년 전 0

djm03178 5년 전 2

kimjh9434 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말