기록방

👉 문제링크 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 🔸 문제 분석 🔸 T번의 테스트 케이스를 돌린다. 계산기는 10진수 4자리 숫자로 0000~9999까지 처리할 수 있다. 4가지 연산 D, S, L, R이 있다. A부터 시작해 B가 되는 최소길이 명령어를 출력한다. 가중치가 없는 최단거리(최소경로) 문제이므로 BFS 를 사용한다. 큐에서 현재 숫자와 지금까지의 연산을 기록할 클래스를 만든다. D : 2n%10000 S : n-1 (n=1이면, 9999) L : (LShift) n = n..

👉 문제링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🔸 문제 분석 🔸 N x M 연구소 격자 맵에 빈 칸은 0, 벽은 1, 바이러스는 2로 입력된다. 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나간다. 벽을 3개 세워서 바이러스가 다 퍼진 후 나올 수 있는 빈 칸의 수 최대값을 출력한다. 3개의 벽을 설치할 위치를 조합으로 구한다. BFS로 바이러스가 퍼진 상태로 만든다. 0의 수를 세서 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOExcept..

👉 문제링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시가 있고, M개의 버스가 있다. M개의 버스는 한 도시에서 다른 도시까지 드는 버스 비용이 있다. 출발 도시부터 도착지 도시까지 버스 비용의 최소 값을 출력한다. 전형적인 다익스트라 알고리즘 문제이다. 그래프에서 한 정점에서 특정 정점까지의 최소비용을 구해야 한다. M개의 버스는 단방향 연결을 나타낸다. 목적지가 나올 때 까지, 각 정점의 최단 거리를 갱신해간다. 목적지에 방문하면 그때의..

👉 문제링크 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 🔸 문제 분석 🔸 0부터 n까지 원소가 1개씩 들어있는 n+1개의 집합에서 입력 연산의 결과를 출력한다. 0은 두 집합의 합집합 연산을 수행한다. 1은 두 집합이 같은 집합인지 확인해, 같으면 "YES" 혹은 "yes", 다르면 "NO" 혹은 "no"를 출력한다. 전형적인 union-find 알고리즘 문제이다. 합집합 연산은 union을 사용한다. 두 집합이 같은 집합인지 확인은 find를 사용해 반환값을 비교한..

👉 문제링크 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 🔸 문제 분석 🔸 n * m 도화지에서 연결된 1의 개수의 최대값을 출력한다. BFS혹은 DFS로 연결된 1을 탐색한다. 연결된 1 무리의 개수와 그 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import..