티스토리 뷰
728x90
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD
- 문제 :
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
- 풀이 :
그래프 탐색 문제였습니다.
그래프를 탐색하는데 가장 높은 Depth를 가진 노드들 중 가장 큰 번호를 찾으면 됩니다.
BFS로 해결하였습니다.
1. ArrayList의 배열을 사용하여 그래프 생성
2. depth와 방문여부를 동시에 확인하기 위해 visited배열을 int 배열로 생성
3. bfs로 탐색하며 시작점을 depth = 1, 이후 depth + 1씩 한다.
4. 탐색이 종료된 후 가장 높은 Depth를 가진 노드들을 찾으며 가장 큰 노드의 번호를 기록한다.
- 소스코드 :
import java.awt.GradientPaint;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// SWEA_1238_Contact_D4_106ms
public class Solution{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int len, start, answer, max;
static Queue<Integer> q;
static ArrayList<Integer>[] graph;
static int[] visited;
public static void main(String[] args) throws IOException {
for (int testCase = 1; testCase <= 10; testCase++) {
st = new StringTokenizer(br.readLine());
len = Integer.parseInt(st.nextToken()) / 2;
start = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
visited = new int[101];
graph = new ArrayList[101];
answer = 0;
max = 0;
for (int i = 0; i < 101; i++) { // ArrayList 배열생성
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < len; i++) { // 입력 받기
graph[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
}
//BFS
q = new LinkedList<Integer>();
q.add(start);
visited[start] = 1;
while(!q.isEmpty()) {
int x = q.poll();
for (int i : graph[x]) {
if (visited[i] == 0 ) {
visited[i] = visited[x] + 1;
q.add(i);
}
}
}
// BFS 종료 후 visited의 MAX를 찾음
for (int i = 0; i < visited.length; i++) {
if (visited[i] >= max) {
max = visited[i];
answer = answer < i ? i : answer;
}
}
sb.append("#").append(testCase).append(" ").append(answer).append("\n");
}
System.out.print(sb.toString());
}
}
320x100
'Algorithm > DFS & BFS' 카테고리의 다른 글
(Java/자바) - 백준(BOJ) 3055번 : 탈출 (0) | 2022.08.24 |
---|---|
(Java/자바) - 백준(BOJ) 13023번 : ABCDE (0) | 2022.08.23 |
(Java/자바) - 백준(BOJ) 1987번 : 알파벳 (0) | 2022.08.18 |
(Java/자바) - 백준(BOJ) 4963번 : 섬의 개수 (2) | 2022.07.19 |
(Python/파이썬) - 백준(BOJ) 2573번 : 빙산 (0) | 2022.07.14 |
댓글
© 2022 WonSeok, All rights reserved