두부의 코딩일기

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 요즘 마법사 상어 시리즈를 풀어보고있는데 파이어스톰 마법을 배웠다고 한다... 위 문제는 아래와 같은 과정을 거친다. 파이어스톰 단계를 L이라고 가정했을 때, (0, 0)을 시작으로 $2^{L}$x$2^{L}$ 크기의 부분 격자로 나눈다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 특정 칸에서 인접해있는 칸 중 얼음이 존재하는 칸이 3개 미만이라면 특정 칸의 얼음..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 위 문제는 맵 격자의 가운데 칸부터 토네이도가 이동을 시작한다. 한 번에 한 칸씩 이동하며 모래는 아래와 같은 비율로 흩날리게 된다. static double[] per = {1,1,2,2,7,7,10,10,5,0}; static int[][] sdx = { {-1,1,-2,2,-1,1,-1,1,0,0}, // 좌 {-1,-1,0,0,0,0,1,1,2,1}, ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 이번 문제는 설명에 너무 자세하게 적혀있어서 풀이할 게 없다. 문제에서 시키는대로 하면 된다. 우선 ArrayList 배열로 선언된 Student 에 학생의 번호와 좋아하는 학생의 번호를 넣어준다. 문제 1, 2, 3번의 조건을 쉽게 해결하려면 우선 순위 큐를 사용하면 된다. public static class Position implements Comparable{ int x; ..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제의 조건 및 구동 순서는 아래와 같다. 1. 벨트가 각 칸 위에 있는 로봇과 함께 움직인다. 2. 가장 먼저 벨트에 올라간 로봇부터 회전 방향으로 한 칸씩 이동한다. (이동하려는 칸의 내구도가 0 이상이며 로봇이 없을 경우) 3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 로봇을 올릴 수 있다. 4. 위의 과정을 내구도가 0인 칸의 개수가 K개 이상일 때까지 반복..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 생각했던 것보다 오래 걸렸던 문제였다. 위 문제에는 빨간 구슬과 파란 구슬 두 가지가 존재한다. 핵심은 빨간 구슬이 10번 이하로 움직여서 구멍에 들어가야한다. 또한, 빨간 구슬과 파란 구슬이 동시에 들어가면 안된다. 한 번의 움직임에 한 방향으로 벽이 나타날때까지 계속 움직일 수 있다. 빨간 구슬을 예로 살펴보겠다. // 빨간 구슬 int ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 전형적인 다익스트라 알고리즘 문제. 최단경로 응용 문제로 진행 과정을 자세하게 적어뒀다. 다익스트라에 대해서 처음 접하시는 분은 아래 링크를 먼저 읽어보는 걸 추천한다. https://sookr5416.tistory.com/160 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 이번 문제는 조건이 많아서 고민할 게 많았다. 구동 순서는 아래와 같다. 택시 위치로부터 가장 가까운 손님을 찾는다. (findPerson) - bfs 가까운 손님의 목적지까지 이동 (goTaxi) - bfs 위 내용을 반복한다. 1. 택시 위치로부터 가장 가까운 손님을 찾는다. public static void findPerson(int x, int ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음에 문제를 잘 못 이해해서 꽤 오랫동안 고민했다. 우선 모든 행과 열을 한 줄로 나열해서 체크해야 한다. 예를 들어, 위 그림처럼 6x6 행렬이 있다면 행 6번, 열 6번 총 12번의 체크를 해야 한다. for (int i=0; i 1) { return false; } 이젠 경사로를 놓았을 때의 경우만 생각하면 된다. 경사로를 놓았을 때 생기는 경우의 수는 2가지이다. 오르막 길 내리막 길 오르막 길, 내리막 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에 이해하기 쉽게 설명이 잘 적혀있으니까 생략하겠다. 위 문제에서는 두 개의 일이 순서대로 이루어진다. 미세먼지 확산: 4방향으로 먼지가 확산된다. 공기청정기 작동: 위 칸과 아래 칸의 바람이 방향이 서로 다르며 한 칸씩 먼지를 밀어낸다. 미세먼지 확산은 dfs 혹은 bfs를 이해하고 있고 관련된 문제를 풀어봤다면 쉽게 해결할 수 있을 것이다. public static void Dust..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 기본적인 bfs 에서 말이 이동할 수 있는 경로만 신경써주면 된다. 말처럼 이동할 수 있는 기회는 K번으로 횟수가 제한되어있으며 벽을 넘을 수 있다. 시작점 (0, 0) 으로 출발해서 (w, h) 까지 최소한의 횟수로 도착하면 된다. 원숭이 상태와 말 상태일 때를 구분해서 돌려주면 쉽게 해결할 수 있다. 1. 원숭이 상태일 경우 1) 이미 방문을 했는지 여부 판단 (visit..