# 유형 : 그래프 , BFS, DFS ,플로이드와샬
# 두 가지 방법으로 풀었다. 첫 번째는 플로이드 와샬 방법, 그리고 두 번째 방법은 평소 많이 사용하던 BFS로 풀었다.
플로이드 와샬 방법으로는 집(출발지) 편의점(거쳐가는 정점) 락 페스티벌(도착점)으로 잡고 알고리즘을 사용하면 된다.
BFS는 인접 리스틀 사용하여 BFS 알고리즘을 완성하면 된다. 꼭 한 방법으로만 푸는게 아니고 여러 방법으로 푸는 것도 알고리즘 실력에도 향상이 되니 여러 방법을 접하고 도전해보는 것을 추천한다.
1) 플로이드 와샬을 이용한 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
package bj;
import java.awt.Point;
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;
public class p9205_floyd {
static int N;
static int arr[][];
static ArrayList<Point> arrList;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(br.readLine());
for(int tc=0; tc<testCases; tc++) {
N = Integer.parseInt(br.readLine());
arrList = new ArrayList<>();
arr = new int[N+2][N+2];
for(int i=0; i<N+2; i++)
for(int j=0; j<N+2; j++)
arr[i][j]=999999;
StringTokenizer st;
for(int i=0; i<N+2; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arrList.add(new Point(x,y));
}
for(int i=0; i<N+2; i++) {
for(int j=0; j<N+2; j++) {
if(i==j)
continue;
Point current = arrList.get(i);
Point next = arrList.get(j);
int dist = Math.abs(current.x-next.x)+Math.abs(current.y-next.y);
if(dist<=1000)
arr[i][j] = 1;
}
}
floyd_warshall();
if(0<arr[0][N+1] && arr[0][N+1]<999999)
System.out.println("happy");
else
System.out.println("sad");
}
}
public static void floyd_warshall() {
for(int k=0; k<N+2; k++) {
for(int i=0; i<N+2; i++) {
for(int j=0; j<N+2; j++) {
if(arr[i][j] > arr[i][k] + arr[k][j])
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
}
}
|
cs |
2) BFS를 이용한 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
package bj;
import java.awt.Point;
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;
public class p9205 {
static int N;
// static int arr[][];
static Point arr[];
static boolean visit[];
static ArrayList<Integer> arrList[];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(br.readLine());
for(int tc=0; tc<testCases; tc++) {
N = Integer.parseInt(br.readLine());
arrList = new ArrayList[N+2];
visit = new boolean[N+2];
for(int i=0; i<N+2; i++)
arrList[i] = new ArrayList<>();
arr = new Point[N+2];
StringTokenizer st;
for(int i=0; i<N+2; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[i] = new Point(x,y);
}
for(int i=0; i<N+1; i++) {
for(int j=i+1; j<N+2; j++) {
float dist = (float) ((Math.abs(arr[i].x - arr[j].x) + Math.abs(arr[i].y -arr[j].y))/50.0);
if(dist <= 20) {
arrList[i].add(j);
arrList[j].add(i);
}
}
}
if(bfs())
System.out.println("happy");
else
System.out.println("sad");
}
}
private static boolean bfs() {
// TODO Auto-generated method stub
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visit[0] = true;
while(!queue.isEmpty()) {
int index =queue.poll();
// System.out.println(index);
if(index == N+1)
return true;
for(int i=0; i<arrList[index].size(); i++) {
// System.out.println(arrList[index].get(i));
if(!visit[arrList[index].get(i)]) {
visit[arrList[index].get(i)] = true;
queue.add(arrList[index].get(i));
}
}
}
return false;
}
}
|
cs |
'백준' 카테고리의 다른 글
| #백준_2174 로봇 시뮬레이션 - Java 자바 (0) | 2020.02.19 |
|---|---|
| #백준_2931 가스관 - Java 자바 (0) | 2020.02.18 |
| #백준_1592 영식이와 친구들 - Java 자바 (0) | 2020.02.16 |
| #백준_1613 역사 - Java 자바 (0) | 2020.02.16 |
| #백준_6593 상범 빌딩 - Java 자바 (0) | 2020.02.15 |
