나그네

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를 진행하며 탐색 경로를 구한다. 이 경로가 ..

16964번: DFS 스페셜 문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. DFS의 결과가 가능한지 구하는 문제다. DFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 orde..

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..

1937번: 욕심쟁이 판다 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 2차원 배열에서 어느 한 점에서 출발해 상하좌우로 점차 증가하는 방향으로만 이동할 수 있을 때 가장 많이 이동할 수 있는 길이를 구하는 문제다. 따라서 dfs로 배열의 모든 점에 대해 가장 긴 이동 거리를 구하고 최댓값을 구했는데 시간초과를 받았다. 시간초과를 해결하기 위해 메모이제이션을 하는 방법밖에 없다고 생각했다. 따라서 visited 배열을 ..

27737번: 버섯 농장 문제 https://www.acmicpc.net/problem/27737 27737번: 버섯 농장 첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다. 버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸 www.acmicpc.net 풀이 버섯 포자를 심을 때마다 개수를 세어준다. DFS로 포자를 심은 부분으로부터 연결되어 심을 수 있는 모든 구간에 포자를 심는다. 포자를 심고 최대 퍼져나갈 수 있는 칸까지 간 다음엔 다시 1부터 시작하고 포자를 심는다. 가능한 모든 공간에 포자를 심은 후에 사용한 포자 수가 0개이거나 사용한 포자 수가 준비한 포자 수보다 많은 경우 버섯 농..

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

15971번: 두 로봇 문제 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 풀이 동굴에서 두 점 A, B에서 각자 최소한으로 움직여 간선 하나를 남겨두고 마주할 수 있을 때 통신이 가능하다. 이때 최단 이동 거리를 구하는 문제다. 처음엔 bfs로 A에서 B까지 도달한 다음 B에서 다시 bfs를 시작해 최단 경로 위에서 B의 이동 거리와 B가 이제 갈 곳까지의 A의 이동 거리의 합이 최소인 것을 찾아줬으나 틀렸습니다를 받았다. 친구에게..