www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import java.util.Scanner; public class Main { static int n; static int[][] cost; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); cost=new int[n][n]; for (int i = 0; i
www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 걱정했는데 swexpert의 플로이드 와샬보다 알고보니 쉬운 문제였다. 거리를 초기화해줄 때 1000(맥주를 마실 수 있는 최대 거리) 보다 크면 -1로 양방향(여기 양방향 처리 안했다 틀렸다)으로 넣어준다. 양방향으로 넣어주는 이유는 시작점과 끝점 둘 중 하나라도 연결이 안되면(중간점과의 간선길이가 1000보다 큰 경우) 시작점 - 중간점 - 끝점 을 연결할 수가 없기 때문이다. 만약 시작점과 끝점 둘다..
나는 연결이 안된 사람을 -1로 써줬다. 플로이드 와샬 알고리즘을 볼 때 s(시작점) 중간노드 (k) e(끝 점) 의 거리를 업데이트 해줄 때 중간에 연결이 안된 사람이거나 (dist[s][k]==-1 || dist[k][e]==-1) 두 지점은 연결되어 있고 dist[s][e]가 연결이 안되어있는 상태인 경우 dist[s][e]==-1 dist[s][e]=dist[s][k]+dist[k][e]로 업데이트를 해줬다. import java.util.Scanner; public class Solution { static int t,n; static int[][] dist; public static void main(String[] args) { Scanner sc=new Scanner(System.in); ..
이런 서로 간의 순위를 알아내는 문제를 만나면 못 풀었었는데 플로이드 와샬 알고리즘이라고 한다. (음... 잊었군) 중간 노드 개념이 어려웠었는데 이렇게 a가 mid를 이기고 mid가 b를 이기면 a가 b를 이김 이런식으로 보니까 이해했다. 백준 순위 문제와 같다니까 그거는 자바로 풀어봐야겠다. function solution(n, results) { var answer = 0; // 1부터 시작 주의 const graph=Array.from({length:n+1},()=>Array(n+1).fill(false)); results.map((item)=>{ const [win,lose]=item; graph[win][lose]=1; //이긴 경우 1 graph[lose][win]=-1; //졌을 경우 -1..