플로이드 와샬6 [자바] 백준 21278 - 호석이 두 마리 치킨 (java) 목차 문제 : boj21278 필요 알고리즘 플로이드 와샬, BFS, 다익스트라 등 최단 거리 알고리즘 아무거나 최단 거리를 구할 수 있는 알고리즘으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 이하와 같다. 1. 모든 건물에 대해 모든 쌍에 대한 최단 거리를 알 수 있다고 해보자. 2. 그렇다면 N개 중 2개의 건물을 고르기로 확정하고, '1'에서 구한 거리 정보로 '최단 시간의 총합.. 2023. 6. 13. [자바] 백준 14588 - Line Friends (Small) (java) 문제 : boj14588 필요 알고리즘 개념 Floyd-warshall 또는 BFS, 그래프 이론 플로이드 와샬 혹은 BFS로 풀 수 있는 그래프 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 결국 서로간의 최단거리를 구해야 함. 그럼 bfs, 플로이드 와샬, 다익스트라 정도가 생각남. 2. O(N^3) 해도 N이 300이라 매우 충분하므로 대충 구현 쉬운 플로이드 와샬로 진행함. 3. 중요한건 일단 위치정보.. 2022. 12. 21. [자바] 백준 2224 - 명제 증명 (java) 문제 : boj2224 필요 알고리즘 개념 플로이드 와샬 (Floyd Warshall) O(N^3)이라 자주 못쓰지만, 쓸 수만 있으면 모든 정점에서 모든 정점으로의 최단경로 파악 혹은 길이 존재하는지 파악이 한방에 가능한 가장 강력한 탐색 알고리즘(대신 느림ㅋ) 플로이드 와샬을 쓸 수 있는 문제이다!! 구현도 엄청 간단하므로 플로이드 와샬을 써보자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a => b 형태일 경우, .. 2022. 9. 2. [코틀린, 자바] 백준 2273 - 줄 서기 (boj kotlin java) 문제 : boj2273 1. 알아야 하는 것 총 5명이 있다고 가정하고 내 앞에 서야 한다고 확정된 학생이 2명이고, 내 뒤에 서야 한다고 확정된 학생이 1명이라고 해보자. 이 정보를 가지고 '각 학생이 설 수 있는 위치의 범위'를 알 수 있을까? 내 앞에 최소 2명은 있어야 하므로 난 무조건 3번째 자리 이상으로 서야 한다. 또한 내 뒤에 반드시 한 명은 있어야 하므로 4번째 이하의 자리에 서야만 한다(5-1=4). 따라서 '설 수 있는 위치의 범위'는 '3 4'가 된다. 즉, 자신의 앞이라고 확정된 인원이 X명, 자신의 뒤라고 확정된 인원이 Y명, 총 N명이라면 범위는 'X+1 N-Y'가 됨을 알 수 있다. 그럼 다음의 경우를 생각해보자. 3 2 1 2 2 3 위의 경우 3의 앞에 2가 서고, 2의 .. 2022. 7. 19. 백준 23258 자바 - 밤편지 (BOJ 23258 JAVA) 문제 : boj23258 개인적으로 오늘 푼 플3 문제보다 몇배는 어려웠다. 심지어 플로이드 와샬 알고리즘을 정확히 이해해야 풀 수 있는 문제라고 추천을 받고 풀게되어서 일단 플로이드 와샬을 써야 한다는 점은 알고 풀게 되었는데 그런데도 엄청 해맸다 ㅠ 아무튼 플로이드 와샬을 써보려면 이 문제는 꼭 풀어봐야 할 것 같다. 플로이드 와샬을 이해하는데 도움이 되는 매우 좋은 문제라 생각한다. 1. '2^C 방울 이상 마시면 안된다'의 의미 우선 이 부분부터가 문제였다. 처음엔 뭔가 장난스럽게, 좀 더 복잡하게 보일려고 이렇게 작성했다고 생각했다. 그래서 2^X, 2^C에서 '2^' 부분은 때고 X, C로만 생각했는데 당연히 제대로 답이 안나왔다. 결론적으로 키 아이디어에 해당하는 부분으로 사실 Ce로 가는 .. 2022. 2. 4. [자바] 프로그래머스 - 순위 [코딩테스트 연습 Lv3] 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%203/%EC%88%9C%EC%9C%84.java 방향 그래프로 표현할 수 있는 문제의 경우 일단 그래프로 그려보면 답이 보이는 경우가 많다. 따라서 일단 무지성으로 그려봤다. 그럼 길찾기 처럼 거리를 한번 재보자! 정확힌 어디까지 갈 수 있는지만 알 수 있으면 된다. arr[i][j]를 대해 i번에서 j번까지의 거리라고 생각하고 표를 작성하면 아래와 같다. 그럼 이쯤에서 이 문제를 풀 수 있는 아이디어를 찾을 수 있다. 저기 '5'의 경우 4명한테 져서 순위가 확정됬.. 2021. 11. 12. 이전 1 다음
