[BOJ] 백준 18352 특정 거리의 도시 찾기 (Swift)
문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 X번 노드에서 도달할 수 있는 도시들의 최단 거리를 구해야 합니다. 간선의 비용이 모두 동일하므로 BFS를 사용해서 풀이할 수 있는 문제입니다. 저는 visited라는 Int 배열을 선언하였고, 값을 X번 노드에서의 최단 거리로 사용하였습니다. visited 배열 중 값이 k와 같은 노드를 출력시켜주었고, 없다면 ..
[BOJ] 백준 20149 선분 교차 3 (Swift)
문제 https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 https://dev-mandos.tistory.com/314 [BOJ] 백준 17387 선분 교차 2 (Swift) 문제 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 https://dev-mandos.tistory.com/313 [BO..
[BOJ] 백준 17387 선분 교차 2 (Swift)
문제 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 https://dev-mandos.tistory.com/313 [BOJ] 백준 17386 선분 교차 1 (Swift) 문제 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net dev-mandos.tistory..
[BOJ] 백준 17386 선분 교차 1 (Swift)
문제 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 풀이 CCW를 사용해 풀이할 수 있습니다. CCW를 사용해 반시계방향이면 1, 시계방향이면 -1, 직선일 때 0을 리턴하도록 하였습니다. 다음과 같이 1, 2, 3, 4 라는 점이 있을 때 123 의 방향과 124의 방향은 반대입니다. 따라서 두 선분은 교차하고 있다고 할 수 있습니다. 하지만 다음과 같은 상황에서는 123과 124의 방향이 반대인데 교차하지 않고 있습니다. 34 선분에 대해서 1과 2에 대한 ..
