[백준] 1260 DFS와 BFS - DFS(깊이우선탐색) + BFS(넓이우선탐색) JAVA

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

1260번: DFS와 BFS

문제해설

가장 기본적인 DFS와 BFS 문제입니다.

다만, 문제 조건의 

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다

해당 조건을 간과하여 코딩하여 오류를 찾는데 시간이 좀 걸렸습니다.

코드

인접리스트로 구현하여 노드의 정보를 저장했습니다.

import java.util.*;


public class Main {
	public static int N, M, V;
	public static ArrayList<Node>[] nodes;
	public static boolean[] visited;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	M = sc.nextInt();
    	V = sc.nextInt();
    	
    	nodes = new ArrayList[N+1];
    	for(int i=1;i<=N;i++) {
    		nodes[i] = new ArrayList<Node>();
    	}
    	
    	for(int i=0;i<M;i++) {
    		int nodeA = sc.nextInt();
    		int nodeB = sc.nextInt();
    		nodes[nodeA].add(new Node(nodeB));
    		nodes[nodeB].add(new Node(nodeA));
    	}    	
    	
    	visited = new boolean[N+1];
    	DFS(V);
    	System.out.println();
    	
    	visited = new boolean[N+1];
    	BFS(V);
    }
    
    public static void DFS(int start) {
    	visited[start] = true;
    	System.out.print(start + " ");
    	Collections.sort(nodes[start]);
    	for(int i=0;i<nodes[start].size();i++) {
    		int endNode = nodes[start].get(i).endNode;
    		if(visited[endNode] == false) {
    			DFS(endNode);
    		}
    	}
    	
    	
    }
    
    public static void BFS(int start) {
    	Queue<Integer> q = new LinkedList<>();
    	visited = new boolean[N+1];
    	q.offer(start);
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {
    		int startNode = q.poll();
    		System.out.print(startNode+" ");
    		
    		Collections.sort(nodes[startNode]);
    		
    		for(int i=0;i<nodes[startNode].size();i++) {
    			int endNode = nodes[startNode].get(i).endNode;
    			if( visited[endNode] == false) {
    				q.offer(endNode);
    				visited[endNode] = true;
    			}
    		}
    	}
    	System.out.println();
    }
}


class Node implements Comparable<Node>{
	int endNode;
	public Node(int endNode) {
		this.endNode = endNode;
	}
	@Override
	public int compareTo(Node other) {
		if(this.endNode > other.endNode) {
			return 1;
		}else if(this.endNode < other.endNode) {
			return -1;
		}else {
			return 0;
		}
	}
}

 

더 간단하게 노드 간의 그래프를 행렬로 표현하여 나타낼 수 있습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static int[][] matric;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        matric = new int[N][N];
        int V = Integer.parseInt(st.nextToken());
        
        for(int i=0;i<M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken()) - 1;
        	int b = Integer.parseInt(st.nextToken()) - 1;
        	
        	matric[a][b] = 1;
        	matric[b][a] = 1;
        }
        
        //DFS 실행
        boolean[] visited = new boolean[N];
        visited[V-1] = true;
        DFS(0, V - 1, visited);
        
        //BFS 실행
        System.out.println();
        BFS(V-1);
    }
    
    public static void DFS(int depth, int now, boolean[] visited) {
    	System.out.print(now + 1+" ");
    	
    	for(int c=0; c<N; c++) {
    		if(visited[c] == true) continue;
    		if(matric[now][c] == 1) {
    			visited[c] = true;
    			DFS(depth + 1, c, visited);
    		}
    	}
    	
    }
    
    public static void BFS(int now) {
    	Queue<Integer> q = new LinkedList<>();
    	boolean[] visited = new boolean[N];
    	q.offer(now);
    	visited[now] = true;
    	
    	while(!q.isEmpty()) {
    		int temp = q.poll();
    		System.out.print(temp+1 +" ");
    		
    		for(int c = 0; c < N; c++) {
    			if(matric[temp][c] == 1 && visited[c] == false) {
    				visited[c] = true;
    				q.offer(c);
    			}
    		}
    		
    	}
    	
    }
    
    
}