목차
- 개요
- 본문
- 1) 문제
- 2) 과정
- 3) 코드 전체
개요
이번에 알고리즘 스터디에서 JAVA를 이용해 백준 11265번 끝나지 않는 파티를 풀었습니다. 이를 정리해보고자 합니다.
11265번: 끝나지 않는 파티
입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸
www.acmicpc.net
본문
1) 문제
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
2) 과정
shortest path니까 다익스트라 알고리즘을 사용하면 되겠지 싶었는데, 자꾸 시간초과가 발생하길래 다른 방법을 찾다 해당 문제를 플로이드 와샬 알고리즘으로 풀어야한단걸 알게되었습니다... 처음엔 오히려 다 구하면 오래 걸리지 않을까? 하며 반신반의했는데 오히려 더 빠르게 풀리는 걸 보고 제 자신의 무지함을 느꼈습니다.. 그렇게 4시간 정도 걸려서 문제를 해결했고 그 과정동안 받은 에러로그 및 개선과정을 깃헙에 적어뒀습니다 ! "내가 왜 틀렸지??" 싶은 분들은 한번쯤 방문하셔서 살펴보시면 도움이 될 것입니다!
해당 문제를 해결하면서 사용한 기본 아이디어는 "한 두개의 출발-목적지의 최단거리를 구하는게 아닌 다수의 경우의 최단거리를 구해야하기 때문에 플로이드 와샬로 최단거리를 dp에 모두 저장한다."였습니다.
그렇게 도출된 풀이 방식은 다음과 같습니다.
0) Input - 기본정보(n,m)를 입력받는다.
1) initialize dp array - dp에 입력받은 i->j까지의 시간을 담는다.
2) floyd warshall - 플로이드와샬 알고리즘으로 mid를 늘려가며 start에서 end까지의 dp(최단거리)값을 갱신해나간다.
3) output - 입력받은 출발지부터 도착지까지의 최단거리가 입력받은 최단거리보다 크다면 ans[0], 아니면 ans[1]을 출력한다.
상세 설명 구성은 Input, Logic, Output으로 구성했습니다. 주석으로도 충분히 많은 설명이 되어 있어 따로 내용을 적진않겠습니다!
2-1) Input
// Constant
static String[] ans = {"Stay here\n","Enjoy other party\n"};
// Variable
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
// Read Method
private static void readLine() throws IOException {st = new StringTokenizer(br.readLine()); }
private static int nextInt() {return Integer.parseInt(st.nextToken());}
// Main
public static void main(String[] args) throws IOException {
// Input
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
readLine();
int n = nextInt(); // 파티장의 크기
int m = nextInt(); // 서비스를 요청한 손님의 수
// initialize dp array
int[][] dp = new int[n][n]; // [i][j] 일때 i에서 j까지의 최단거리를 저장함.
for(int i=0;i<n;i++){
readLine();
for(int j=0;j<n;j++) dp[i][j] = nextInt();
}
}
2-2) Logic
public static void main(String[] args) throws IOException {
// Logic
for(int mid=0; mid<n;mid++){ // mid가 for문의 가장 바깥에 있어야하고, 작은수부터 늘려나가야 올바른 값이 나온다.
for(int start=0;start<n;start++){
for(int end=0;end<n;end++){
if(end==mid) continue; // end==mid일때의 값은 갱신할 필요가 없음.
dp[start][end] = Math.min(dp[start][end],dp[start][mid]+dp[mid][end]);
}
}
}
}
2-3) Output
// Output
for(int i=0;i<m;i++){
readLine();
bw.append(ans[dp[nextInt()-1][nextInt()]>nextInt() ? 0: 1]);
} bw.flush();
이번엔 BufferedWriter로 출력을해봤는데 sysout만 사용하는 것보다 속도가 많이 향상되어 맘에 들었습니다 ㅎㅎ!
3) 전체코드
그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!
소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.
https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/shortest_path/BOJ11265.java
GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비
명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비를 위한 스터디입니다. Contribute to Park1122/Algorithm-Study development by creating an account on GitHub.
github.com
'알고리즘(JAVA 사용) > Shortest Path' 카테고리의 다른 글
[알고리즘풀이]백준 1916 : 최소비용 구하기 JAVA (0) | 2021.12.31 |
---|---|
[알고리즘풀이]백준 18352 : 특정 거리의 도시 찾기 JAVA (0) | 2021.12.31 |
[알고리즘풀이]백준 1753 : 최단경로 JAVA (0) | 2021.12.31 |
[알고리즘풀이]백준 11403 : 경로 찾기 JAVA (0) | 2021.12.31 |