728x90
한국사가 끝나고,
어제부터 코테 1일 1문제를 시작했다.
백준 9205번 (https://www.acmicpc.net/problem/9205) 문제를 푸는데,
BFS인줄 알고, 이차원 배열 맵을 만들어서 위치를 표시하고 사방탐색하면서 나아가도록 구현했는데 뭔가 이상하다는 느낌을 받았다.
검색해보니 플로이드 와샬 알고리즘으로 푸는 것이다.
오랜만에 푸니까 다 까먹었다.
플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용한다.
DP 기반으로 아래 두 거리 중 최솟값으로 갱신한다.
x 노드에서 y 노드로의 거리 vs x 노드에서 k (= 거쳐가는 노드, 경유지) 로의 거리 + k 에서 y노드로의 거리
3중 for 문 = 시간복잡도가 N³ 이라는 점을 유의하며 사용해야 한다.
아래 블로그를 참고하면서 개념을 이해했다.
24. 플로이드 와샬(Floyd Warshall) 알고리즘
지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나...
blog.naver.com
[Algorithm] Floyd-Warshall 알고리즘 with JAVA
들어가며플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘입니다. 3중 for문을 사용해서 전체 경로에 대해 지나칠 수 있는 노드를 점차 확장하며 가장 적
jundyu.tistory.com
# 9205 (맥주 마시면서 걸어가기) Java 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder answer = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t --> 0) {
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
List<Point> locations = new ArrayList<>(); // 상근이네 집, 편의점, 페스티벌 좌표 저장
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());
locations.add(new Point(x, y));
}
boolean[][] isAbleToGo = new boolean[n + 2][n + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = i + 1; j < n + 2; j++) {
if (findManhattan(locations.get(i), locations.get(j)) <= 1000) {
isAbleToGo[i][j] = isAbleToGo[j][i] = true;
}
}
}
for (int k = 0; k < n + 2; k++) { // Floyd Warshall
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
if (isAbleToGo[i][k] && isAbleToGo[k][j]) isAbleToGo[i][j] = true;
}
}
}
answer.append(isAbleToGo[0][n + 1] ? "happy" : "sad").append("\n");
}
System.out.print(answer);
}
static int findManhattan(Point p1, Point p2) {
return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}728x90
'Algorithms > Algorithm' 카테고리의 다른 글
| 페이지 교체 알고리즘과 LRU Cache (0) | 2022.12.02 |
|---|---|
| 백트래킹 (Backtracking) (0) | 2022.11.24 |
