PS/백준

[백준] - 자리배정 10157

https://www.acmicpc.net/problem/10157 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 시계방향으로 배열을 초기화 시켜준다. 배열의 범위를 벗어나거나 이미 자리가 배정된 경우 방향을 전환해준다. 자리 배정이 끝나면 대기 순서가 K인 자리(x, y)를 찾아 출력한다. [Java] import java.io.*; import java.util.*; public class Main { // 위, 오른쪽, 아래쪽, 왼쪽 순으로 방향을 전환 (시계방향) static int d..

백준 1753 - 최단 경로 (다익스트라)

[문제 해결] 다익스트라를 이용한 최단경로 문제이다. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private static boolean visited []; private static int dist[]; private static ArrayList graph = ne..

백준 안전영역 2468 - java

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [문제 해결] 해당 지역의 높이만큼 비가오면 해당 지역은 물에 잠긴다 주어진 지역들의 높이 만큼 비가 온다고 가정하고 bfs를 탐색하면 된다. 비가 와서 높이가 4이하인 지역이 모두 잠긴다면 안전 영역이 5가되고 높이가 6인만큼 비가오면 안정영역이 4가 된다. 이렇게 주어진 높이들 만큼 비가 온다고 가정하고 안전 영역의 최대 값을 구하면 된다. import java.io.BufferedReader; im..

알고리즘 수업 - 깊이 우선 탐색

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 예제 케이스는 통과하는데 제출하면 틀리시는 분들을 위해 반례 드립니다. 1% ~ 3% 70% [입력] [입력] 6 4 1 5 1 3 2 3 1 2 1 4 1 5 4 6 정답 정답 1 0 0 0 0 1 2 0 4 0 3 [java] import java.io.BufferedReader; import java.io.IOExcep..

백준 - 점프왕 쩰리 (Small) - Java

https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net [문제 해결] 저는 DFS를 이용한 완전 탐색으로 문제를 해결 하는데, BFS로도 문제를 해결하실 수 있습니다. [java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static int[][]..

백준 알고리즘 수업 - 너비 우선 탐색 4 (24447) - Java

https://www.acmicpc.net/problem/24447 24447번: 알고리즘 수업 - 너비 우선 탐색 4 정점 1번에서 정점 2번, 정점 4번을 순서대로 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 4, 3, 0이다. 너비 우선 탐색 www.acmicpc.net [문제 해결] 방문한 순서를 기록할 배열 seq[]와, 깊이를 기록할 visited[] 배열을 만들어준다. 그래프가 만들어지면 인접 정점들을 오름차순 정렬을 해준다. bfs를 돌려준다. 주의 할점은 visited, seq 배열과 값을 곱하고 더해줄 ans변수를 long으로 해주어야 한다. import java.io.BufferedReader..