728x90
반응형
문제
https://www.acmicpc.net/problem/1260
풀이 방법
각 인접 정보를 저장한 후, DFS, BFS로 출력해주면 되는 간단한 문제이다. DFS는 재귀호출로 BFS는 큐를 사용했다.
제출 코드
public class BJ_1260_DFS와BFS {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int[][] adjMatrix = new int[N + 1][N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int to = Integer.parseInt(st.nextToken());
int from = Integer.parseInt(st.nextToken());
adjMatrix[to][from] = 1; //무향 그래프이므로 양쪽에 다 넣어주기
adjMatrix[from][to] = 1;
}
dfs(V, new boolean[N+1], N, adjMatrix);
System.out.println();
// bfs
bfs(V, N, adjMatrix);
}
private static void dfs(int v, boolean[] selected, int N, int[][] adjMatrix) {
selected[v] = true;
System.out.print(v+" ");
for (int i = 1; i <= N; i++) {
if(adjMatrix[v][i]==1 && !selected[i]) dfs(i, selected, N, adjMatrix);
}
}
private static void bfs(int start, int N, int[][] adjMatrix) {
Queue<Integer> queue = new LinkedList<>();
boolean[] selected = new boolean[N+1];
queue.offer(start);
selected[start] = true;
while(!queue.isEmpty()){
int temp = queue.poll();
System.out.print(temp+" ");
for (int i = 1; i <=N; i++) {
if(adjMatrix[temp][i] == 1 && !selected[i]) {
queue.offer(i);
selected[i] =true;
}
}
}
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 2669 직사각형 네 개의 합집합의 면적구하기 (JAVA) (0) | 2022.02.22 |
---|---|
[BJ] 백준 1759 암호만들기 (JAVA) (0) | 2022.02.22 |
[BJ] 백준 2477 참외밭 (JAVA) (0) | 2022.02.21 |
[BJ] 10157 자리배정 (JAVA) (0) | 2022.02.19 |
[BJ] 13305 주유소 (0) | 2022.02.19 |