본문 바로가기

코딩 테스트

[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 경우의수 뒤에 붙는.. 더보기
[Java] 12996 Acka 문제 문제 BOJ 알고리즘 캠프에 강사로 참여하고 있는 dotorya, kesakiyo, hongjun7은 301호에서 도원결의를 맺고 프로젝트 아이돌 그룹 Acka을 결성했다. Acka의 데뷔 앨범에는 총 S개의 곡이 수록될 예정이다. 각각의 곡은 세 사람중 적어도 한 명이 불러야 한다. 즉, 어떤 곡은 두 사람이 불러도 되고, 세 사람이 모두 함께 불러도 된다. 세 사람이 녹음해야 하는 곡의 수가 주어질 때, 앨범을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오. 두 앨범 A와 B가 있을 때, 참여한 사람이 다른 곡이 존재한다면, 두 앨범은 다른 앨범이라고 한다. 입력 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다.. 더보기
[Java] 1707 이분 그래프 문제 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을.. 더보기

티스토리툴바