알고리즘/그래프 관련 Algorithm & 그래프 문제 (7) 썸네일형 리스트형 백준(BOJ) 11404: 플로이드 https://www.acmicpc.net/problem/11404 기본 Floyd-Walshall문제이다. 문제 조건에 두 도시간의 노선은 하나만 아니라는 조건이 있는데 이것만 입력받을 때 적절하게 처리해 주면 된다. //다익스트라=그래프 있어야 함. 벨만 포드: 그래프 없어도 됨. 플로이드. 그래프 있어야 함. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Testing3{ static int[][]map; stat.. 백준(BOJ) 1865: 웜홀 #bellman https://www.acmicpc.net/problem/1865 (복습. 벨만포드: 음의주기가 있을때도 최단거리를 구할수 있고 음의주기가 있다면 판별할 수 있다. n번 반복하여 매번 모든 간선에 대해 dsit를 갱신한다. n-1번째에 dist가 갱신된다면 그것은 음의 주기가 있다는 것이다) 출발했던 지점으로 다시 돌아왔을때 시간이 되돌아간(시간이 줄어든)경우가 있는지를 묻고 있다. 기본적으로 벨만포드는 음의주기가 있을때를 포함하여 한점에서 다른 모든 정점까지의 거리를 구하기 위한 알고리즘이다. 그런 알고리즘이 이러한 출발정점으로 되돌아 왔을 경우에 별다른 코드 변경없이 쓰일수 있다는 것이다(물론 시간초과를 해결하기 위한 boolean변수는 필요했다). 어떻게 이것이 가능할까? 문제에서는.. 백준(BOJ) 1238: 파티 https://www.acmicpc.net/problem/1238 출처: https://steady-coding.tistory.com/106 다익스트라(Dijkstra)는 한정점에서 그 정점을 제외한 다른 모든 정점까지의 최단거리를 구할때 쓰이는 알고리즘이다. 그렇다면 다른 모든 정점에서 그 하나의 정점까지의 각각의 최단거리는 어떻게 구할까? 입력을 반대로 받아서 다익스트라 알고리즘을 적용하면 된다. 이 문제에서 배운것: 여러개의 정점에서 한정점으로 가는 각각의 최단거리는 출발점과 도착점에 대해 받은 정보를 반대로 적용하여 다익스트라 알고리즘을 적용하면 쉽게 구할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import j.. 백준(BOJ) 1753: 최단경로 https://www.acmicpc.net/problem/1753 처음에 인접리스트로 풀었다. 통과가 되었다. 하지만 방향그래프인만큼 인접행렬로 풀려고 시도를 하였다 => 메모리 초과가 났고 아래 글을 발견했다. 관련내용은 "3."번이다. https://www.acmicpc.net/board/view/34516 따라서, 방향그래프라고 해서 반드시 인접행렬을 사용해야만 하는 것은아니다. 아래는 인접행렬로 구현한 메모리초과가 나는 풀이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Testing3 { static class Point { int vertex; int weight.. 백준(BOJ) 11657: 타임머신 /* 출력 초과를 논리적으로 계산하는 습관. 처음에는 출력초과가 나왔다. 이후 dist배열의 int를 long으로 바꾸니 통과되었다. 이 문제에서 출력 초과가 발생하는 이유는 -1을 출력해야 하는 상황에서 각 도시로 가는 최단 거리들을 출력하기 때문입니다. 질문하신 내용처럼 기존 dist에 들어있는 INF가 초과되어 overflow가 발생하지는 않으나, 이 문제는 가중치가 음수인 것이 허용되는 벨만-포드 알고리즘 문제입니다. 음수 사이클이 존재한다면 끝 없이 최소값이 갱신될 수 있고 이 때문에 출력초과가 발생하는 것입니다. 왜 이 때문에 출력초과가 발생하느냐? 가 궁금하실텐데 결론부터 말하자면 underflow때문입니다. 문제에서 주어진 조건인 정점의 개수가 500개, 간선의 개수가 6000개, 최소 가.. 백준(BOJ) 2667: 미로 탐색 https://www.acmicpc.net/problem/2178 BFS로 품. 객체지향 설계 2주차 과제와 연관된 문제라 풀어봄. Collection class에 요소로 배열을 넣고 그 각각의 배열에 y,x좌표를 넣는 방식이 익숙치 않았음. 왜 DFS가 아닌 BFS냐는 의문에 아직 정확히 답은 못하지만, DFS로도 풀수 있긴함. 하지만 한번 방문된 적이 있다면 다음에 다시 방문했을때 그것은 무조건 최단거리가 아님을 이용하는 것에서 DFS보다는 BFS가 적당할 것이라는 생각. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; import java... 백준(BOJ) 1260 : DFS와 BFS (그래프 탐색 쌩기초) https://www.acmicpc.net/problem/1260 기본적으로 dfs, bfs를 구현할 수 있는 지 문제이다. 상징성 있는 문제로 구실을 갖추기 위해 넣어 놓는다. from sys import stdin from collections import defaultdict from collections import deque def dfs(graph, visited, start): if(start not in visited): visited.add(start) print(start, end=' ') for v in range(len(graph)): if(graph[start][v]==1): dfs(graph, visited, v) def bfs(graph, start): que=deque([st.. 이전 1 다음
