본문 바로가기

전체 글

[Java] 16920 확장게임 문제문제구사과와 친구들이 확장 게임을 하려고 한다.이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다.한 칸 위에 성이 두 개 이상인 경우는 없다.게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다.제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다.플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이.. 더보기
[Java] 12851 숨바꼭질 2 문제문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.둘째 줄에는.. 더보기
[Java] 14940 쉬운 최단거리 문제문제지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.입력지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.출력각 지점에서 목표지점까지의 거리를 출력한다.원래 갈 수 없는 땅인 위치는 0을 출력하고,원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.문제 풀이BFS를 통한 문제이다. 처음 map의 값을 입력 받을 때 값이 2인(목표지점인) 위치를 기록해 두었다가 해당 위치를 시작으로 상.. 더보기
[Java] 6118 숨바꼭질 문제문제재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다.농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다.헛간의 개수는 N(2 문제 풀이그래프를 이용한 BFS 문제.자바 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class N6118 { private static boolean[] checked; private static List[] road; private static int distance, destination, cnt; public static void main(String[] args.. 더보기
[Java] 2644 촌수계산 문제문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때,주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 .. 더보기
[Java] 16973 직사각형 탈출 문제문제크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.격자판의 각 칸에는 빈 칸 또는 벽이 있다.직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.입력첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다.0은 빈 칸, 1은 벽이다.마지막.. 더보기
[Java] 2252 줄 세우기 문제문제N명의 학생들을 키 순서대로 줄을 세우려고 한다.각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다.M은 키를 비교한 회수이다.다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.학생들의 번호는 1번부터 N번이다.출력첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에.. 더보기
[Java] 2133 타일 채우기 문제 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 문제 풀이 DP 문제이다. 우선 3xN 칸이기 때문에 N이 홀수 일 경우는 타일을 채울 수 없어 답은 무조건 0이다. 즉, N이 짝수 일 경우만 구하면 된다. N = 2일 경우는 3개이다. N = 4 일 경우는 N=2일 경우의 수가 2개 있는 것이므로 3 * 3개의 수가 필요하고 추가로 아래와 같은 형태 2가지가 더 필요하다. 즉 3 * 3 + 2 = 11개 가 된다. N = 6 의 경우는 N = 4 인 경우에 N = 2 인경우를 붙이는 거로는 조금 모자라다. N=4 경우에서 발행한 2개의 모양이 N-2 경우의수 뒤에 붙는.. 더보기

티스토리툴바