public class Main
{
static int n, m, v; // 정점, 간선, 시작점
static ArrayList<Integer>[] al;
static boolean visited[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stz = new StringTokenizer(br.readLine());
n = Integer.parseInt(stz.nextToken());
m = Integer.parseInt(stz.nextToken());
v = Integer.parseInt(stz.nextToken());
al = new ArrayList[n + 1];
visited = new boolean[n + 1];
// al 초기화
for(int i=0; i <= n; i++){
al[i] = new ArrayList<>();
}
// 간선 정보 입력
for(int j=0; j < m; j++){
stz = new StringTokenizer(br.readLine());
int p1 = Integer.parseInt(stz.nextToken());
int p2 = Integer.parseInt(stz.nextToken());
al[p1].add(p2);
al[p2].add(p1);
}
// 오름차순 정렬 하기
for(int k = 0; k <= n; k++){
Collections.sort(al[k]);
}
dfs(v);
visited = new boolean[n + 1];
System.out.println();
bfs(v);
}
private static void dfs(int s) {
visited[s] = true;
System.out.print(s + " ");
for(int tmp : al[s]){
if(!visited[tmp]){
dfs(tmp);
}
}
}
private static void bfs(int s){
Queue<Integer> q = new LinkedList<>();
Queue<Integer> ans = new LinkedList<>();
visited[s] = true;
q.add(s);
ans.add(s);
while(!q.isEmpty()){
int now = q.poll();
for( int tmp : al[now]){ // 차례대로
if(!visited[tmp]){ // 만약 방문 안했을 때
q.add(tmp);
visited[tmp] = true;
ans.add(tmp);
}
}
}
while(!ans.isEmpty()){
int a = ans.poll();
System.out.print(a + " ");
}
}
}
그래프 탐색: 하나의 정점에서 모든 정점을 차례대로 한 번씩 방문하는 것
모두 이미 방문했으면 이전으로 돌아감
n m v
n : 정점
m : 간선
v : 시작점
ex) 1 3 => arrList[1] = 3
arrList[3] = 1
1, 2, 3, 4
al[1] = 2, 3, 4
al[2] = 1, 4
al[3] = 1, 4
al[4] = 1, 2, 3
=> sort 안해서 틀렸었었다 문제 잘 읽기!
dfs:
1 -> 2 -> 4 -> 3
bfs:
1 -> 2 -> 3 -> 4
import java.util.*;
public class Main
{
static final int MAX_N = 1001;
static int N,M,V;
static int[][] board = new int[MAX_N][MAX_N];
static boolean[] visited = new boolean[MAX_N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); M = sc.nextInt();
V = sc.nextInt();
for(int i = 0; i < M; i++){
int a = sc.nextInt();
int b = sc.nextInt();
board[a][b] = board[b][a] = 1;
}
dfs(V);
}
static void dfs(int node){
visited[node] = true;
System.out.print(node + " ");
for(int next = 0; next < N + 1; next++){
if(!visited[next] && board[node][next] != 0)
dfs(next);
}
}
}
import java.util.*;
public class Main
{
static int N, M, V;
static Queue<Integer> queue;
static int[][] board = new int[1001][1001];
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
V = sc.nextInt();
for(int i = 0; i < M; i++){
int a = sc.nextInt();
int b = sc.nextInt();
board[a][b] = board[b][a] = 1;
}
bfs(V);
}
static void bfs(int start){
queue = new LinkedList<>();
queue.add(start);
visited = new boolean[1001];
visited[start] = true;
System.out.print(start + " ");
while(!queue.isEmpty()){
int tmp = queue.remove();
for(int i = 1; i < N + 1; i++){
if(board[tmp][i] == 1 && visited[i] == false){
visited[i] = true;
queue.add(i);
System.out.print(i + " ");
}
}
}
}
}
'알고리즘' 카테고리의 다른 글
<백준> 2805번 자바 알고리즘 [이분 탐색] (0) | 2022.03.06 |
---|---|
<백준> 1920번 자바 알고리즘 [이분 탐색] (0) | 2022.02.08 |
<백준> 1707번 자바 알고리즘 [BFS][이분 그래프] (0) | 2022.01.25 |
<백준> 7562번 자바 알고리즘[BFS] (0) | 2022.01.24 |
<백준> 2206번 자바 알고리즘[BFS] (0) | 2022.01.21 |