본문 바로가기

ALGORITHM

 (212)
백준 6593 상범 빌딩 (Java) 1. 문제 링크 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력 받으면서 갈 수 있는 곳은 true, 갈 수 없는 곳은 false로 저장한다. (시작점과 끝점은 따로 변수에 저장한다.) 한 층씩 입력받고 list에 추가해서 3차원을 관리했다. 시작점을 넣고 BFS로 큐의 크기만큼 돌리면서 동서남북상하를 확인하고 갈 수 있는 곳은 큐에 넣고 그 자리를 false로 바꾼다. 전체 BFS를 몇번했는지 출력한다. 4. 코드 import java.io.BufferedReader..
백준 14502 연구소 (Java) 1. 문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 조합을 이용해 벽을 세울 3 곳을 찾는다. +) map을 복제하여 조합마다 결과에 영향을 미치지 않게 한다. 2. 조합으로 선택된 3 위치에 벽을 세운다. 3. 큐에 바이러스의 위치를 모두 넣어두고 사방탐색을 하면서 바이러스를 퍼뜨린다. 4. 탐색이 끝난 후 바이러스가 있는 수를 세고 최댓값일 경우 갱신한다. 4. 코드 import java.io.BufferedReader; import java.io.InputSt..
백준 20055 컨베이어 벨트 위의 로봇 (Java) 1. 문제 링크 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 내구성과 로봇의 유무를 링크드리스트로 관리했다. 내구도 0인 칸이 K개가 될 때까지 3 함수를 반복한다. 함수1은 내구도와 로봇 리스트의 마지막을 꺼내 처음에 넣는다. 함수2는 움직일 수 있는 로봇이면 한 칸 씩 옮기고 리스트 내용을 수정한다. 올리는 위치에 로봇 유무를 확인하고 로봇을 추가한다. 4. 코드 import java.io.BufferedReader; import java.i..
백준 10814 나이순 정렬 (Java) 1. 문제 링크 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 Member 객체를 사용하는데 Comparable을 상속받아서 나이 기준으로 비교한다. Arrays.sort()로 배열을 정렬하고 그대로 출력하면 된다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.A..
백준 10773 제로 (Java) 1. 문제 링크 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 수를 stack에 push고, 0을 입력 받을 때 pop 한다. 모든 입력이 끝나면 stack에서 pop하여 모든 수를 더한 값을 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.io.IOException; pub..
백준 14719 빗물 (Java) 1. 문제 링크 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 해당 블록 기준으로 왼쪽 전부 중 최대 높이 블록, 오른쪽 전부 중 최대 높이 블록을 구한다. 둘 중 작은 높이가 기준이 되는 블록보다 작은 경우에만 물이 고인다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public s..
백준 2636, 2638 치즈 (Java) 1. 문제 링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받으면서 전체 치즈의 수를 셌고 치즈가 다 녹으면 끝이 난다. find()로 DFS 하면서 외부 좌표는 out 배열에 저장했다. 외부 좌표를 다 찾았으면 melt로 치즈를 녹인다. melt()에서는 치즈가 나오면 out 배열의 값을 비교해서 두 변 이상이 외부에 노출되었다면 queue에 넣는다. (2638번) melt 끝나고 오면 전체 치즈 수에서 큐의 크기를 빼고, 큐에서 빼서 현 좌표를..
백준 12865 평범한 배낭 (Java) 1. 문제 링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 전형적인 DP 문제이다. 해당 무게가 되는지 여부를 알고 지금 물건의 가치가 더 높은지 판단해서 저장한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static..

티스토리툴바