https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 BFS를 사용한 4방향 델타 탐색 문제입니다 일반 문제와 다른 부분은, 미로가 1초마다 내려온다는 점이죠. 때문에 한 회차마다 이동을 하며 이동이 모두 끝난 뒤 모든 칸을 1만큼 내리는 과정을 반복합니다. 상하좌우 + 대각선 8방향 탐색 + 제자리 val dx = intArrayOf(-1, -1, -1, 0,..

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라, 최단 경로 설명 레이저를 쐈을 때, 방향을 좌측 혹은 우측으로 90도 회전할 수 있는 거울을 최소로 놓아 레이저를 목표 지점까지 도달시키는 문제입니다. 저는 BFS를 응용하여 풀이했는데요. 한 거울마다 90도씩 회전할 수 있기 때문에 현재 레이저의 방향 역시 좌표에 저장해야 합니다. 따라서 저는 n ..

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 누적 합 설명 직사각형이 장애물에 걸리지 않게 시작점에서 도착점으로 갈 수 있는지 판단하는 문제입니다. 처음에는 BFS를 돌리며 각 좌표마다 직사각형의 넓이만큼 맵을 확인하는 방법으로 풀었으나, 시간초과를 맞이했습니다 어떻게 할까 고민을 하다가, 맵에 미리 장애물의 크기를 매핑해놓자고 생각했습니다...

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹 접근법 DFS / BFS를 이용한 그룹화 문제입니다. 특이한 점은 0 ~ 15 범위 내 숫자가 주어져 벽의 위치를 알려준다는 점인데요. 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어집니다. 예를 들어 (0, 0)의 경우..

https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 맨 위에서 맨 아래까지 도달할 수 있는지 판단하는 문제입니다. dfs / bfs를 응용하여 풀 수 있는데요. 맨 위의 모든 점에서 dfs / bfs를 시작하여 최하층에 도달할 수 있다면 성공입니다. 좌측부터 1번째 통로를 탐색한 결과, 벽에 막혀 가지 못합니다. 2번..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 연구소에 바이러스가 퍼졌습니다. 바이러스가 퍼지기 전에 다행이도 벽을 3개 세울 수 있을 때, 벽을 적절히 배치하여 안전구역(바이러스가 퍼지지 않는 구역)을 최대화하는 문제입니다. 주어지는 바이러스는 1개 이상이기 때문에, 초기 큐에 바이러스의 위치를 모두 넣어놓고 BFS를 돌려 여러 위치에서 바이러스를..

https://www.acmicpc.net/problem/1385 1385번: 벌집 첫째 줄에는 당신이 있는 방의 번호 a와 출구가 있는 방의 번호 b가 주어진다.1 ≤ a, b ≤ 1,000,000) www.acmicpc.net 난이도 : 플래티넘 5 태그 : 구현, 그래프이론, 그래프탐색, 너비우선탐색 설명 벌집(2292)에 비해 꽤나 매운맛인 벌집 문제 입니다. 위와 같이 생긴 벌집을 대상으로 최단거리를 찾는 BFS을 돌려 풀 수 있겠다는 생각은 빨리 들었으나, 벌집의 모양을 그래프로 나타내는 것에 상당히 어려움을 느꼈습니다. 벌집을 그래프로 나타내라! 그래프는 위와 같이 벌집을 약간 회전시켜 2차원 배열 형태로 나타낼 수 있습니다. 예를 들어 500 * 500 사이즈 배열의 경우, (250, 25..

https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 난이도 : 플래티넘 3 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체, 이분 매칭 설명 소수 판정 + 이분 매칭 문제입니다. 이분 매칭에 관해서는 아래 글을 참고해주세요. https://uknowblog.tistory.com/444 [알고리즘] 이분 매칭 (Bipartite Matching) 이분 매칭을 간단히 이야기하면 연애 매칭 프로..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 이분 탐색, 너비 우선 탐색, 분리 집합 설명 N개의 섬들은 M개의 다리를 통해 서로 연결 되어있습니다. 각 다리에는 중량 제한이 있고, 중량 제한을 초과할 경우 다리가 무너집니다. 한 번에 이동할 수 있는 중량의 최댓값을 구하는 문제입니다. 가장 빨리 떠오른 생각은 브..

https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 기하학, 분리 집합 설명 통신 범위가 직/간접적으로 겹치는 부대는 하나의 부대처럼 행동합니다. 즉, 통신범위가 겹치는 그룹을 모두 같은 그룹으로 묶어 몇 개의 그룹이 나오는지 구하는 문제입니다. 그룹화와 서로 다른 그룹의 개수를 구한다는 점에서 분리집합과 유니온 파인드를 사용할 수 있을 것 같습니다. 분리 집..