백준 - 1260번 DFS와 BFS - java

https://www.acmicpc.net/problem/1260

 

중요한 테스트 케이스
입력
3 2 1
1 3
2 1

출력
1 2 3
1 2 3

접근법

기본적인 DFS, BFS 풀려고 했는데, 기존에 주어진 간선 데이터를 정렬해줘야 원하는 순서대로 탐색이 이루어진다

for(int i = 0; i < e.length; i++) {
	if(e[i][0] > e[i][1]) {
		int temp = e[i][1];
		e[i][1] = e[i][0];
		e[i][0] = temp;
	}
}

 

입력받은 간선을 먼저 앞에 값이 더 크다면 자리를 바꿔주고

Arrays.sort(e, (o1, o2) -> {
			if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]);
			else return Integer.compare(o1[0], o2[0]);
		});

해당 2차원 배열을 정렬시켜준다

그 후 정렬된 순서대로 간선 데이터를 넣어줘서 그래프를 완성한 후에 DFS, BFS를 수행하면 된다

간선 데이터를 정렬하는 방법도 있지만, 일단 그래프를 완성하고 각 노드들의 간선정보에서 정렬시켜도 가능은 하겠다

 

소스

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static Node[] node;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		int v = sc.nextInt();
		
		int[][] e = new int[m][2];
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < 2; j++) {
				e[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 0; i < e.length; i++) {
			if(e[i][0] > e[i][1]) {
				int temp = e[i][1];
				e[i][1] = e[i][0];
				e[i][0] = temp;
			}
		}
		
		Arrays.sort(e, (o1, o2) -> {
			if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]);
			else return Integer.compare(o1[0], o2[0]);
		});
		
		node = new Node[n+1];
		boolean[] visit = new boolean[n+1];
		for(int i = 1; i <= n; i++) {
			node[i] = new Node(i);
		}
		
		
		for(int i = 0; i < e.length; i++) {
			int start = e[i][0];
			int end = e[i][1];
			
			node[start].edge.add(node[end]);
			node[end].edge.add(node[start]);
		}
		dfs(v, visit);
		bfs(v, node);
		
	}
	public static void dfs(int idx, boolean[] visit) {
		Node curNode = node[idx];
		visit[idx] = true;
		System.out.print(idx + " ");
		for(int i = 0; i < curNode.edge.size(); i++) {
			Node findNode = curNode.edge.get(i);
			if(!visit[findNode.index]) {
				dfs(findNode.index, visit);
			}
		}
	}
	
	public static void bfs(int idx, Node[] node) {
		boolean[] visit = new boolean[node.length+1];
		Queue<Node> q = new LinkedList<Node>();
		q.offer(node[idx]);
		System.out.println("");
		while(!q.isEmpty()) {
			Node curNode = q.poll();
			visit[curNode.index] = true;
			System.out.print(curNode.index + " ");
			for(int i = 0; i < curNode.edge.size(); i++) {
				Node findNode = curNode.edge.get(i);
				if(!visit[findNode.index]) {
					q.offer(findNode);
					visit[findNode.index] = true;
				}
			}
		}
	}
}
class Node {
	int index;
	ArrayList<Node> edge;
	Node(int index){
		this.index = index;
		this.edge = new ArrayList<Node>();
	}
}