어쩌다보니 컴퓨터학부

[백준] 28215: 대피소 (JAVA)

풀이너무 오랜만에 접한 알고리즘 문제 + 긴 지문으로 인해 시간이 좀 오래 걸렸다 .. 문제가 좀 헷갈리고 복잡해서 그렇지 사실 dfs를 적용할 수 있으면 간단하게 풀 수 있을 문제였다. 정답 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N, K; static int[][] arr; static int minMaxDist = Integer.MAX_VALUE; // 가장 큰 거리값이 가장 작을 때의 거리 static int[] selected; // 선택..

수천 년 동안 잊혀진 고대 문명의 유적을 발견하게 되었습니다. 이 유적지는 5×5 격자 형태로 되어 있으며, 각 칸에는 다양한 유물의 조각이 배치되어 있습니다. 유물 조각은 총 7가지 종류로, 각각 숫자 1부터 7로 표현됩니다.[1] 탐사 진행3×3 격자 선택당신은 고고학자로서 5×5 격자 내에서 3×3 격자를 선택하여 격자를 회전시킬 수 있습니다. 선택된 격자는 시계 방향으로 90도, 180도, 270도 중 하나의 각도만큼 회전시킬 수 있습니다. 단, 선택된 격자는 항상 회전을 진행해야만 합니다.예를 들어, 다음과 같이 유적지가 존재한다고 가정해보겠습니다.만약 회전 중심 좌표를 (3,3)으로 설정하고, 90도 회전하면 유적지는 다음과 같이 바뀌게 됩니다.회전 목표가능한 회전의 방법 중 (1) 유물 1차..

1번부터 P번까지 P 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!(1) 게임판의 구성게임판은 N×N 크기의 격자로 이루어져 있습니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.게임은 총 M 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 P번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.게임판에서 두 ..

예제 입력 1 7 80 1 31 1 70 7 61 7 10 3 70 4 20 1 11 1 1예제 출력 1NONOYES 풀이유니온 파인드 알고리즘의 기초같은 문제이다. 직관적으로 알고리즘을 구현하면 된다. 정답 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int[] node; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..

문제N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.예제 입력 13예제 출력 11 2 31 3 22 1 32 3 13 1 23 2 1 풀이바로 직전에 순열을 사용한 문제를 풀어서 나름 수월하게 푼 문제였다.주의할 점은 한번 백트래킹을 돌릴 때마다 visited뿐만 아니라 sb도 초기화 해줘야 한다는 점이다. 정답 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static int N..

문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2..

문제찬솔이는 블로그를 시작한 지 벌써 N$N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.입력첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.출력첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다. 예제 입력 1 복사5 21 4 2..

문제N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부..

문제N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져..

문제석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 ..