[백준] DFS와 BFS - java

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B1260 {
static int N, M, V;
static boolean[] visited;
static ArrayList<Integer>[] list;
	
public static void main(String[] args) throws IOException {
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	st=new StringTokenizer(br.readLine()," ");
	N=Integer.parseInt(st.nextToken());
	M=Integer.parseInt(st.nextToken());
	V=Integer.parseInt(st.nextToken());
	
	visited=new boolean[N+1];
	list=new ArrayList[N+1];
	
	for (int i = 1; i <=N; i++) {
		list[i]=new ArrayList<Integer>();
	}
	for (int i = 0; i < M; i++) {
		st=new StringTokenizer(br.readLine()," ");
		int a=Integer.parseInt(st.nextToken());
		int b=Integer.parseInt(st.nextToken());
		list[a].add(b);
		
	}//for


	for (int i = 1; i < N+1; i++) {
		Collections.sort(list[i]);
	}	
	for (int i = 1; i < N+1; i++) {
		System.out.println("i:"+i+","+list[i]);
	}
	for (int i = 1; i < N+1; i++) {
		visited[i]=false;
	}
	System.out.print(V+" ");
	dfs(V);

	System.out.println();
	for (int i = 1; i < N+1; i++) {
		visited[i]=false;
	}
	bfs(V);
}//main
private static void dfs(int V) {
	visited[V]=true;
	
	//System.out.print(V+" ");
	for(int i=0; i<list[V].size(); i++) {
		int a=list[V].get(i);
		if(!visited[a]) {
			System.out.print(a+" ");
			visited[a]=false;
			dfs(a);
		}
	}
}
private static void bfs(int V) {
	Queue<Integer> que=new LinkedList<>();
	que.add(V);
	visited[V]=true;
	while(!que.isEmpty()) {
		int q=que.poll();
		System.out.print(q+" ");
		for(int i=0; i<list[V].size(); i++) {
			int a=list[V].get(i);
			if(!visited[a]) {
				que.add(a);
				visited[a]=true;
			}
		}
	}
	
	
}



}//Main-class

 

이렇게 풀었지만, 첫번째 케이스만 통과하고 나머지는 다 실패...

양방향처리를 안해서 그런 것같다.

 

처음 단방향 처리했을때 ->

list[a].add(b);

 

⭐양방향처리 ->

list[a].add(b);
list[b].add(a);

 

 

위에 코드가 틀렸던점-2

 

while문 안에서 새로운 값으로 계속 돌아야 하는데 , 초기 입력값을 넣었었다. list[V] -> list[q]

while(!que.isEmpty()) {
		int q=que.poll();
		System.out.print(q+" ");
		for(int i=0; i<list[q].size(); i++) {
			int a=list[q].get(i);
			if(!visited[a]) {
				que.add(a);
				visited[a]=true;
			}
		}

 

 

고친코드

• 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호
• 정점은 1부터 시작하니, 인덱를 맞춰주기위해 +1 해줌
• 정점의 수만큼 ArrayList 선언
• 두 정점의 번호를 list에 넣어주는데 ,양방향이니 좌표를 바꿔서도 서로 넣어주기
• 작은 값부터 정렬
• dfs함수 전에, visiited를 모두 false 처리해준다.
• dfs는 재귀함수로 구현하였기 때문에 main함수에서 첫값을 출력 해주고 실행
•  dfs-> 재귀함수로 돌면서 해당 수의 arrayList를 방문하면서 방문하지 않은 값  실행
• bfs로 가기전에 visited를 모두 false 처리
• Queue를 선언하여 , 초기값을 que에 넣어주고 visited도 true 로 바꿔주고
• while문을 돌린다. 
• Queue에 담긴 값을 빼서, list[queue에서 뺀 값]  모든 값을 que에 넣어주고
• 선입선출이므로, 먼저들어온 값이 나간다.

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B1260 {
static int N, M, V;
static boolean[] visited;
static ArrayList<Integer>[] list;
	
public static void main(String[] args) throws IOException {
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	st=new StringTokenizer(br.readLine()," ");
	N=Integer.parseInt(st.nextToken());
	M=Integer.parseInt(st.nextToken());
	V=Integer.parseInt(st.nextToken());
	
	visited=new boolean[N+1];
	list=new ArrayList[N+1];
	
	for (int i = 1; i <=N; i++) {
		list[i]=new ArrayList<Integer>();
	}
	for (int i = 0; i < M; i++) {
		st=new StringTokenizer(br.readLine()," ");
		int a=Integer.parseInt(st.nextToken());
		int b=Integer.parseInt(st.nextToken());
		list[a].add(b);
		list[b].add(a);
	}//for


	for (int i = 1; i < N+1; i++) {
		Collections.sort(list[i]);
	}	
	for (int i = 1; i < N+1; i++) {
		System.out.println("i:"+i+","+list[i]);
	}
	for (int i = 1; i < N+1; i++) {
		visited[i]=false;
	}
	System.out.print(V+" ");
	dfs(V);

	System.out.println();
	for (int i = 1; i < N+1; i++) {
		visited[i]=false;
	}
	bfs(V);
}//main
private static void dfs(int V) {
	visited[V]=true;
	
	//System.out.print(V+" ");
	for(int i=0; i<list[V].size(); i++) {
		int a=list[V].get(i);
		if(!visited[a]) {
			System.out.print(a+" ");
			visited[a]=false;
			dfs(a);
		}
	}
}
private static void bfs(int V) {
	Queue<Integer> que=new LinkedList<>();
	que.add(V);
	visited[V]=true;
	while(!que.isEmpty()) {
		int q=que.poll();
		System.out.print(q+" ");
		for(int i=0; i<list[q].size(); i++) {
			int a=list[q].get(i);
			if(!visited[a]) {
				que.add(a);
				visited[a]=true;
			}
		}
	}
	
	
}



}//Main-class