https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
알고리즘 분류 : BFS, DFS
더보기
public class Main {
static Myscanner sc = new Myscanner();
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static int[][] adj = new int[1001][1001];
static final int inf = Integer.MAX_VALUE;
static boolean[] Dvisited = new boolean[1001];
static boolean[] Bvisited = new boolean[1001];
public static void main(String[] args) {
int N = sc.nextInt();
int M = sc.nextInt();
int V = sc.nextInt();
//adj 초기화
for(int r =0; r<1001;r++){
for(int c= 0; c<1001;c++){
adj[r][c] = (r == c ? 0 : inf);
}
}
for(int idx = 0; idx<M;idx++)
{
int s = sc.nextInt();
int e = sc.nextInt();
adj[s][e]=adj[e][s] =1;
}
out.print(V);
DFS(V);
out.println();
out.print(V);
BFS(V);
out.close();
}
private static void DFS(int v) {
Dvisited[v] = true;
for(int idx =1;idx<adj[0].length;idx++){
if((adj[v][idx]!=inf && adj[v][idx]!=0) && (!Dvisited[idx])){
out.print(" " + idx);
DFS(idx);
}
}
}
private static void BFS(int v) {
Queue<Integer> q = new LinkedList<>();
Bvisited[v] = true;
q.offer(v);
while(!q.isEmpty())
{
int size = q.size();
for(int sz = 0; sz<size;sz++)
{
int here = q.poll();
for(int idx = 1; idx<adj[0].length;idx++)
{
if((adj[here][idx]!=inf && adj[here][idx]!=0) && (!Bvisited[idx])){
q.offer(idx);
Bvisited[idx]= true;
out.print(" "+idx);
}
}
}
}
}
}
BFS와 DFS의 정석을 물어보는 문제인 것 같다.
DFS는 재귀로, BFS는 Queue를 이용하여 해결 완료!
'PS' 카테고리의 다른 글
[BOJ] 2667번: 단지번호붙이기(DFS) (0) | 2017.06.07 |
---|---|
[BOJ] 1012번 : 유기농 배추(DFS) (0) | 2017.06.07 |
[BOJ]1697번 - 숨바꼭질 (0) | 2017.06.06 |
[BOJ] 2568번 : 전깃줄 - 2 (0) | 2017.06.01 |
[BOJ] 1051번 - 숫자 정사각형 (0) | 2017.05.29 |