🔗 문제 링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 💡 문제 풀이 및 해석 평범한 BFS 문제로 본다면, 모든 지점에서 BFS 알고리즘을 구현하여 실행하면 된다. 적록색약과 아닌 상황을 구분해야 하므로, 아래와 같은 과정을 거쳐야 한다. 3-1. 적록색맹이 아닌 사람에 대해서 BFS로 검사한다. 3-2. 적록색맹인 사람은 R -> G 로 바꿔서 검사한다. ⭐️ 정답 코드 및 설명 import javax.naming.PartialResultException; import java.awt.imag..
G4
🔗 문제 링크 2194번: 유닛 이동시키기 첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 www.acmicpc.net 💡 문제 풀이 및 해석 "시작점 -> 도착점"의 최소거리를 구해야 한다는 점에서 BFS로 풀어야 한다 생각했다. 단, queue에 들어간 모든 원소가 빠져나가는 것을 1회로 지정해야 한다. 이 때, 움직이는 Unit은 동서남북으로 한칸씩 움직일 수 있는데, 장애물이 설치된 구역이거나 맵의 바깥쪽으로는 이동할 수 없다. 동서남북으로 이동시에 방향에 맞게 유닛이 이동하는 변이 금지구역에 들어..
🔗 문제 링크 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 💡 문제 풀이 및 해석 N의 범위가 100 이하이므로, 1N번 방에서 1N번 방까지 가는 최소값 거리를 모두 구해도 1초안에 해결되는 문제다. 모든 방에서 모든 방까지 가는 최소의 거리를 다익스트라를 통해서 구한다. 이 최솟값들을 모든 방에 더해준다. 가장 값이 작은 방이 모이기 최적화된 방이다. 값이 같은 경우, 번호가 낮은 수가 출력되어야 한다. ⭐️ 정답 코드 및 설명 #include #include #include #include #defin..
🔗 문제 링크 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 및 해석 문제의 조건대로 풀면된다. 단, 사전 작업으로 해야할 일이 있다. 이 나라는 이번 회차(인구 이동 당일)에 인구 이동이 일어났는가 국경선이 열린 이웃한 나라들의 집합은 어떻게 처리할 것인가 인구가 이동하지 않은 것은 어떻게 알 것인가 더 자세한 풀이는 코드의 주석에 있으니 코드의 흐름대로 읽으면 이해할 수 있을 것이다. ⭐️ 정답 코드 및 설명 #include #include #include #define end..
🔗 문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 💡 문제 접근 가장 먼저 접두사를 어떤 순서로 검사할지 정해야 하는데, 여기서 문제는 이 기준을 어떻게 정할 것인지다. 일단, 최소한 길이가 긴 전화번호가 짧은 전화번호의 접두사가 될 일은 없는데, 이런 방식으로 풀면 뒤의 모든 전화번호들을 검사해야 되기 때문에, 시간초과가 났다. 여기서 정렬을 하면서 힌트를 얻은 것이 있는데, string을 정렬하면 [123..
🔗 문제 링크 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 💡 문제 풀이 및 해석 CCTV는 최대 8개이다. 모든 경우를 생각하면, 최악의 경우 (4번 CCTV가 64개 있을 때, 실제로는 3방향이니 24보다 많이 작다.) 4^8 (모든 CCTV의 모든 방향 체크) \* 64 (맵의 복사) \* 24 (CCTV가 보는 방향 체크) = 100,663,296이다. bruteforce한 방법으로 찾을 수 있다. 나머지는 문제 조건 그대로 구현해주면 된다. ⭐️ 정답 코드 및 설명 #include #in..
🔗 문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 및 해석 먼저 가로, 세로 조건이 8이하이다. 따라서 전체 칸은 64칸이다. 3개의 모든 기둥을 박아야 하므로 64개의 칸 중에서 3개를 선택하는 조합, 그리고 그 상태에서 BFS를 진행한다고 하면, 최대 $64\times63\times62\over3\times2\times1$ $\times64 = 2,666,496$ 이 된다. 이를 토대로 완전탐색을 진행하기로 하였다. 먼저 64개의 칸중 3개의 칸을 조합으로 구성한다. 그 구성이 실제로 가능하면..
🔗 문제 링크 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 💡 문제 풀이 및 해석 공기가 한 번에 다 퍼지게 해야된다. 따라서 모든칸에서 퍼지게 해야되므로 모든 칸에서 로직이 작동되게 해야된다. 현재 칸에서 퍼지게하고, 다음칸을 퍼지게하면, 이미 먼지가 퍼진 상태에서 로직이 실행되므로 먼지가 퍼지는 배열을 따로 만들어줘야 한다. 먼지가 다 퍼지면, 공기가 순환되게 해야된다. 이 때, 공기청정기로 들어오는 방향으로 1칸씩 땡기고, 공기청정기에서 나오는 칸만 0으로 처리해주면 된다. 마지막으로 모든 칸의 먼지..
