나그네

2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 모눈종이 위의 몇 가지 직사각형을 제외한 공간의 수와 각각의 넓이를 오름차순으로 출력하는 문제다. 먼저 2차원 배열을 만들고 직사각형을 채워야 하는데 입력은 모눈종이의 좌표로 입력되는 반면 배열의 인덱스와 맞추기 위해서 2중 for문을 사용해 (x1, y1)부터 (x2, y2)까지 -1로 색칠을 해준다. 배열이 -1이 아닌 공간에 대해 bfs..

2638번: 치즈 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 공기에 두 면이 접촉해 있는 치즈는 사라진다. 발상이 중요한 문제로 치즈를 기준으로 탐색할지, 공기를 기준으로 탐색할지 기준을 잘 세워야 하는 문제다. 정답 풀이 이 문제에서 같은 시간에 사라지는 치즈가 모두 사라진 뒤 동시에 공기가 침투한다. 따라서 치즈가 사라지는 로직과 공기가 퍼지는 로직이 턴제로 진행되야 한다. 중요! 모눈종이의 맨 가장자리는 치즈가..

23034번: 조별과제 멈춰! 문제 https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 풀이 처음에는 X, Y 정점부터 시작하는 최소 스패닝 트리(MST)를 구해줬는데 당연히 시간초과를 받았다. 그래서 생각한 다음 방법은 처음부터 MST를 구해놓은 다음 X와 Y 사이의 가장 큰 가중치를 가지는 간선을 제거해 주는 방법이었다. 처음에는 MST의 간선을 이을 때마다 어느 정점에서 이어졌는지를 기록하고 역추적하는 방식으로 구현했다. 그러나 여..

16940번: BFS 스페셜 문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. BFS의 결과가 가능한지 구하는 문제다. BFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 order 배열을 만들고 먼저 방문해야 하는 정점과 연결된 간선이 앞으로 오도록 간선들을 재정렬 한다. 그리고 BFS를 진행하며 탐색 경로를 구한다. 이 경로가 ..

5214번: 환승 문제 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 하이퍼튜브라는 간선을 통해 정점 간 최단 거리를 구하는 문제다. 각 하이퍼튜브에 포함된 간선들을 서로 이어주면 메모리 초과가 나게 된다. 따라서 M개의 하이퍼튜브 정점을 만들고 하이퍼튜브를 정점으로 생각하고 하이퍼튜브에 포함된 정점들과 이어준다. 그리고 BFS를 통해 최단 경로를 찾으면 된다. 코드 #include using namespace..

5427번: 불 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 입력 형식과 주어진 횟수의 테스트 케이스를 반복하는 점을 제외하고 4179번 불! 문제와 완전히 똑같은 문제다. 4179번 불! 문제의 풀이도 아래 링크에 있으니 풀이를 참고하면 좋을 것 같다. [4179번 불! 문제] | [4179번 불! 풀이] 각 테스트 케이스마다 다음 과정을 반복한다. 접근법은 상근이와 불에 대해 각각 BFS를 사용하는 것이다. 각각에 대해 1부터 시작해 이동..

17071번: 숨바꼭질 5 문제 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다. 처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고..

4179번: 불! 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다. 틀린 풀이 BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

9019번: DSLR 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 D, S, L, R 쿼리를 사용해 A에서 B로 가는 최소 쿼리를 구하는 문제다. BFS로 문제를 해결할 수 있으며 시간초과에 유의해야 한다. visited 배열은 몇 번째 방문인지 나타내는 정수와 해당 정수까지 도달하는 최단 쿼리를 담고 있다. 처음에 L, R 쿼리 때문에 A, B를 string으로 수를 입력받아 또 정수로 바꾸고.. 이런 과정을 거쳤으..