[Java] 백준 2109 (순회강연) Gold 4

Problem : https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net Approach 우선순위 큐를 사용한 그리디(Greedy) 알고리즘 문제이다. 먼저 pay 기준 내림차순으로 정렬된 우선순위 큐가 필요하다. pay가 같을 경우에는 day가 더 작은 것이 우선이다. 그리고 주어진 입력 d의 최대 크기만큼의 cost 배열을 선언한다. cost[i] 는 i일에 얼마짜리 강의를 하는지를 저장한다. cost 배열의 총..

→2021.05.19

Algorithm/Baekjoon Online Judge

[Java] 백준 16933 (벽 부수고 이동하기 3) Gold 1

Problem : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Approach BFS문제이다. 백준 14442 (벽 부수고 이동하기 2) 문제에 조건이 하나 더 달린 문제이다. 여기서의 visited배열은 4차원 배열이다. visited[n][m][k][a] 는 (n, m) 위치를 k번 벽을 부신 채로 낮(a = 0) 혹은 밤(a = 1)에 방문했다는 뜻이다. 문제 풀이의 주요 로직은 다음과 같다. 낮이라..

→2021.05.16

Algorithm/Baekjoon Online Judge

[Java] 백준 14442 (벽 부수고 이동하기 2) Gold 3

Problem : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Approach 대표적인 BFS문제이다. 일단 visited[i][j][k] 는 (i, j) 위치에 k번 벽을 부순 채로 도달했는지를 나타내는 배열이다. 문제를 푸는 주요 BFS 로직은 다음과 같다. 현재 위치에서 상하좌우 방향으로 벽이 아니라면 cnt++ 한 후, 이동한다. (이 때 visited 배열에 벽을 부순 횟수는 증가시키지 않고 표시..

→2021.05.16

Algorithm/Baekjoon Online Judge

[Java] 백준 16954 (움직이는 미로 탈출) Gold 4

Problem : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 변하는 방법은 위에서 아래로 한 칸씩 내려오는 방식이다. 문제를 푸는 로직은 다음과 같다. 현재 위치가 벽이 아니라면, 현재 위치 포함, 상하좌우 대각선4방향으로 이동한다. 벽을 위에서 아래 방향으로 한 칸씩 내린다. 무한 루프를 방지하기 위해 방문 여부를 나타내는 flag 변수를 하나 둔다...

→2021.05.15

Algorithm/Baekjoon Online Judge

[Java] 백준 3055 (탈출) Gold 5

Problem : https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net Approach 이동 가능한 곳이 동적으로 변하는 환경에서의 BFS문제이다. 문제를 푸는 주요 로직은 다음과 같다. 다음에 물이 찰 예정인 곳은 비버가 방문할 수 없으니 물을 먼저 전파시키고 비버를 이동시킨다. 물을 전파시킨다. 비버를 이동할 수 있는(물이 차지 않은) 곳들을 방문한다. 즉, 비버따로 물따로 각각 BFS가 수행되어야 한다. (ps. cnt 배열을 사용하지 않고 Point 클래..

→2021.05.15

Algorithm/Baekjoon Online Judge

[Java] 백준 12886 (돌 그룹) Gold 5

Problem : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net Approach DFS를 사용하여 풀이한 문제이다. BFS로도 풀이가 가능한 것 같다. 새로 만든 숫자와 기존 숫자를 이용하여야 하기 때문에 DFS가 먼저 생각이나서 DFS로 풀이하였다. 먼저 처리할 수 있는 예외를 보자. (a + b + c) % 3이 0이 아니라면 세 숫자를 어떻게 선택하더라도, 서로 같게 만들 수 없다. 문제 풀이 로직은 다음과 같다. 숫자 a, b, c..

→2021.05.14

Algorithm/Baekjoon Online Judge

[Java] 백준 14502 (연구소) Gold 5

Problem : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Approach 완전탐색(BruteForce)과 BFS를 함께 사용하는 문제이다. 문제 풀이 주요 로직은 다음과 같다. 0인 곳들 중 3군데를 골라서 벽을 세운다. 벽을 3개 세웠으면 그 상태에서 BFS를 수행하여 바이러스를 전파시킨다. 전파 시킨 뒤에 0의 개수를 찾는다. 모든 경우를 다 탐색하여, 안전한 구역의 최대 개수를 구한다. Code import java.io.*; import j..

→2021.05.14

Algorithm/Baekjoon Online Judge

[Java] 백준 6087 (레이저 통신) Gold 4

Problem : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net Approach BFS + DP 문제라고 볼 수 있다. 특정 위치 (x, y)를 방문하는 방법은 여러 방법이 있는데, 그 중 방향 전환을 최소로 하는 방문을 찾는 문제이다. 문제에서 거울이라는 개념이 나오는데, 쉽게 말하여 방향이 변하는 곳엔 거울을 놓을 수 밖에 없다. 따라서, 목표 위치 (x, y)를 방문하는 방법 중, 방향 전환이 최소인 방문을 찾으면 된다. cha..

→2021.05.13

Algorithm/Baekjoon Online Judge

[Java] 백준 1963 (소수 경로) Gold 4

Problem : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net Approach 소수를 찾는 알고리즘과 BFS 개념으로 풀 수 있는 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 먼저 간단하게 에라토스테네스의 체 개념을 이용하여 1 ~ 9999 사이의 숫자들 중 소수를 판별한다. 그리고 난 뒤 현재 숫자에서 숫자 하나만 변경하며 BFS를 수행한다. 숫자를 하나씩 바꾸는 부분을 구현하는게 꽤 까다로울 수 있다. String을 사용할까도 생각해봤지만,..

→2021.05.13

Algorithm/Baekjoon Online Judge

[Java] 백준 14395 (4연산) Gold 5

Problem : https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net Approach BFS문제이다. 하지만 배열을 사용하여 풀이한다면, 메모리초과를 만날 것이다. Set 에 방문한 곳들만 추가하여, 메모리를 절약하여야 한다. 이것이 가능한 이유는 1 ~ t범위 안에 실제로 방문할 수 있는 숫자는 전체 숫자 대비 몇개 안되기 때문이다. 문제 풀이에 앞서 입력에 따라 간단히 처리할 수 있는 부분과, 필요한 로직을 단순화 시켜보자. s == t..

→2021.05.11

티스토리툴바