본문 바로가기

Algorithm/BOJ45

[백준] 2178번 미로 탐색 자바 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 이 문제는 진짜 BFS의 정석 같다. 처음에 오른쪽 왼쪽으로 이동하는 것만 담았다가 벽에 막혀서 위나 왼쪽으로도 다시 올라갈 수 있다는 점을 깨닫고 다시 상하좌우로 dr, dc배열을 바꾼거랑 visited배열을 int가 아니라 boolean으로 처음 쓰고 바꾼 거 말고는 나름 빨리 푼 것 같다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo.. 2022. 3. 4.
[백준] 14719번 빗물 자바 문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 풀이 ✔️ 알고리즘 1. 빗물 block[][] 배열에 받아두기 2. block배열의 맨 아래 행부터 위로 올라가면서 고인 빗물세기 3. 블록 처음 만났을 경우, 빗물이 고일 수 있으므로 start변수에 true로 설정해두기 4. start변수가 true이면서 다시 블록을 만났을 경우 end변수에 true로 설정하기 5. 그리고 다시 빈 곳을 만났을 경우 end변수 false로 바꾸기 6. 한 행의 반복이 끝났는데 end변수가 true.. 2022. 3. 4.
[백준] 1149번 RGB거리 자바 문제 (DP) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 DFS로 모든 경우에 한해 값을 계산하고 최소값을 갱신하는 방법으로 풀었는데 시간초과가 떴다. 구글링해보니 dp로 생각보다 간단하게 풀 수 있었다. 행렬의 크기를 [N][3]으로 잡아서 행은 집의 개수, 열은 RGB를 나타내는 개수로 각 집의 색상을 어떤 것을 칠하느냐에 따라 dp배열을 갱신한다. 모든 칠하는 경우의 개수를 보게 되므로 그 전 집의 색깔 중에서 최소값을 바로 택해도 가능하다. 소스 코드 imp.. 2022. 2. 11.
[백준] 14502번 연구소 자바 문제 (DFS, 브루트포스 알고리즘) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 세상에나 완전탐색 문제였다. 난 뭐 논리적으로 푸는 줄 알았는데 구글링해보니 그냥 모든 경우에 한해 벽 세우고 탐색하면서 안전구역의 최대값을 구하는 거였다... 나는 벽 세우는 것과 바이러스 퍼져나가는 것 둘 다 DFS로 구현했다. 그리고 minCount와 count 두 개의 변수를 이용해 답을 구했는데, 아래 코드에서 count는 해당 경우의 벽또는 바이러스의 개수 카운트이고, 이 수가 작을수록 안전구역의 개수가 커지는 것이므.. 2022. 2. 2.
[백준] 14888번 연산자 끼워넣기 자바 문제 (브루트포스 알고리즘) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 사용되는 연산자를 해당 연산자의 인덱스번호를 perm_data에 담는다. 예를 들어 '+'가 1개, 'x'가 2개 이면 perm_data = {0, 2, 2} 이런 식으로 담기게 된다. 이 배열을 조합하여 모든 경우에 해당 되는 연산자 순서를 구하고, 구하는 경우마다 계산결과를 구해 답을 갱신한다. 소스 코드 import java.util.Scanner; public c.. 2022. 2. 2.
[백준] 10971번 외판원 순회 자바 문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 전체 도시를 순회하는 경우, 어느 도시에서 출발하든지 최소비용이 동일하다는 사실을 이해하면 순열을 이용하여 모든 탐색에 한하여 최소비용을 구하면 된다. 예를 들어, 3번 도시에서 출발하여 다음과 같은 순서로 순회했을 때가 최소 비용이라고 해보자. 3 → 2 → 0 → 1 → 3 이 순서는 어떠한 시작점으로 바꿔도 위와 같은 최소비용이 나온다. ex) 2 → 0 → 1 → 3 → 2 ex) 0 → 1 → .. 2022. 2. 2.

티스토리툴바