문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 ..
너비우선탐색
문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..
문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물..
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 379 258 200 68.966% 문제 상우는 재미있는 게임을 생각해냈다. 동전 9개를 아래 그림과 같이 3행 3열로 놓는다. H는 앞면, T는 뒷면을 의미한다. H T T H T T T H H 게임의 목적은 이 동전의 모양을 모두 같은 면(H나 T)이 보이도록 하는 것이다. 단, 하나의 동전만을 뒤집을 수는 없고, 한 행의 모든 동전, 한 열의 모든 동전 또는 하나의 대각선 상의 모든 동전을 한 번에 뒤집어야 한다. 그런 식으로 세 개의 동전을 뒤집는 것을 '한 번의 연산'으로 센다. 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다. 오랜 시간 생각한 끝에 위의 경우는 두 번의 연산으로 가능하다는 것을 알아냈고, 또, 이..
import java.io.*; import java.util.*; public class Laboratory { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static BufferedReader br; static StringTokenizer st; static int n, m; static int res = Integer.MIN_VALUE; static int[][] map, copyMap, virusMap; public static void main(String[] args) throws IOException{ input(); solve(0); System.out.println(res); } static void input(..
import java.io.*; import java.util.*; class Point_1 { int x; int y; Point_1(int x, int y) { this.x = x; this.y = y; } } public class AlgoSpot { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static BufferedReader br; static StringTokenizer st; static int n, m; static int[][] board; static int[][] dp; public static void main(String[] args) throws IOException{ input(); System.ou..
import java.io.*; import java.util.*; class Floor { int num; int cnt; Floor(int num, int cnt) { this.num = num; this.cnt = cnt; } } public class StartLink { static BufferedReader br; static StringTokenizer st; static int f, s, g, u, d; static Floor ans; static boolean[] checked; public static void main(String[] args) throws IOException{ input(); bfs(); if(ans == null) System.out.println("use the..
import java.io.*; import java.util.*; class Rect { int x1; int y1; int x2; int y2; Rect(int x1, int y1, int x2, int y2) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } } public class Logo { static BufferedReader br; static StringTokenizer st; static int n; static int ans; static boolean[] checked; static Rect[] rectArr; static Queue q; public static void main(String[] args) throws IO..
import java.io.*; import java.util.*; public class Puzzle { static BufferedReader br; static StringTokenizer st; static final int[] dx = {-1, 1, 0, 0}; static final int[] dy = {0, 0, -1, 1}; static String input = ""; static final String ans = "123456780"; static HashMap map = new HashMap(); public static void main(String[] args) throws IOException { input(); solve(); } static void input() throws..
import java.io.*; import java.util.*; class Node { int num; int cnt; Node(int num, int cnt) { this.num = num; this.cnt = cnt; } } public class HideAndSeek { static BufferedReader br; static StringTokenizer st; static int N, K; static int ans; static boolean[] checked; public static void main(String[] args) throws IOException{ input(); solve(); System.out.println(ans); } public static void input(..
