나그네

27498번: 연애 혁명 문제 https://www.acmicpc.net/problem/27498 27498번: 연애 혁명 신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 www.acmicpc.net 풀이 이미 성사된 사랑 관계는 포기하도록 하지 않아야 하기 때문에 반드시 포함되는 간선이 있어야 한다. 그리고 사랑 관계가 K 각 관계를 이루지 않아야 하므로 사이클이 없다(트리). 즉, 반드시 포함되어야 하는 간선이 있는 최소 스패닝 트리(MST)를 구현하는 문제다. 이 문제에선 포기하도록 만든 애정도의 합이 최소가 되어야 하므로 최대 스패닝 트리를 구하고 가중치의 합을 모..

11780번: 플로이드 2 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 제목부터 노골적으로 플로이드-워셜 알고리즘을 사용하는 문제임을 보여준다. 그리고 각 정점에서 다른 정점으로 갈 때 최단 경로 중 하나를 출력해줘야 하므로 path 배열을 만들어 최단 경로가 갱신될 때마다 i -> k의 경로, k -> j의 경로를 중복되는 k를 제외하고 합쳐준다. 이를 vector의 insert 함수를 사용해서 합쳐서 만들어줬다. 그리고 p..

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 배열을 ..

9370번: 미확인 도착지 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 먼저 가장 큰 접근법은 G-H는 반드시 지나야 하므로 S -> G -> H -> ? 또는 S -> H -> G -> ? 이 최단 경로여야 한다. 따라서 S -> G, S -> H, G -> H, G -> ?, H -> ? 의 최단 거리를 구해야 한다. 즉, 간선 거리는 항상 양수고 몇몇 정점간 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다. 따라서 ..

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의 이동 거리의 합이 최소인 것을 찾아줬으나 틀렸습니다를 받았다. 친구에게..

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씩 증가하도록 해서 시간을 계산했다. 큐..