2931번: 가스관 www.acmicpc.net 문제 읽기 쓸데없이 시간을 너무 많이 쓴 문제이다.. 좀 허탈한데.. 처음에는 M에서부터 Z까지 이어진 파이프로 이동하면서 더 이상 이동하지 못하는 부분이 있으면 해킹 당한 것으로 생각하고 해당 지점의 상하좌우를 보며 문제를 풀었다. 예제도 다 나왔는데 21%에서 계속 틀려서 질문 게시판도 다 뒤져봤지만, 글도 별로 없을 뿐더러 있는 반례도 다 맞다고 나왔다. 진짜 다른 어딘가에서 틀린 거 같았는데 도저히 찾지를 못했다!! 그래서 그냥 그렇게 탐색해서 지점을 찾지 말고, 모든 빈 칸을 돌면서 상하좌우를 보고 파이프를 연결해야 할 지 판단하는 방식으로 바꾸었다. 맵의 크기도 25x25면 매우 작기 때문에 완탐으로도 충분했다. 그냥 완탐으로 푸는 게 정신 건강..

1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 읽기 N개의 지점, M개의 도로와 W개의 웜홀(각각 양방향, 단방향)이 연결된 그래프가 주어진다. 도로는 시간 비용이 양수이고, 웜홀은 시간 비용이 음수라고 했으므로, 도로를 양의 가중치, 웜홀을 음의 가중치로 보면 되므로 밸만 포드를 사용하여 해결할 수 있다. 다만 문제에서 구하는 것은 최단 거리 그 자체가 아니라, 출발 지점에서 여행을 하고 돌아왔을 때, 시간이 출발 시점보다 더 전으로 가 있을 수 있는지 궁금한 것이다. 이 경우는 음의 가..

흔히 그래프에서 최단 거리를 구하는 알고리즘은 다익스트라를 떠올리기 쉽다. 하지만 다익스트라는 음수 가중치가 있는 경우에는 사용이 불가능하다. 다익스트라에 대한 자세한 설명과 과정들은 다음 링크에서 볼 수 있다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory.com 그럼 음수 가중치가 있는 그래프에 다익스트라를 적용하면 어떻게 되는지 한 번 해보자. 음수 가중치에 다익스트라? 다음 예시를 보자. 위 그래프에 다익스트라를 적용해보자. 시작점을 1로 하여 다른 모든 노드로의 최단 거리를 다익스트..

9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 읽기 일단 처음에 읽었을 때는 다익스트라로 풀면 되겠다 생각이 들었고, 그 사이에 g와 h 사이의 도로를 지나갔다면 별도의 배열로 표시해주자고 생각했다. 하지만! 예제는 나왔지만 제출했더니 틀렸다(근데 예제가 너무 유하게 줘서 웬만하면 예제는 다 맞고 내면 틀리는 거 같다. 그래서 정답 비율이 25%..) 그래서 질문 게시판 뒤져보니 이런 말들이 있었다. 글 읽기 - 반례를..모르겠습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.ne..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 읽기 일단 처음 문제를 읽었을 때는 그리디한 방식이 떠올랐다. 큰 숫자가 앞으로 올수록 좋을 것 같다고 생각했기 때문에, 맨 앞부터 숫자가 들어갈 자리를 정하고, 그 뒤의 숫자들 중에서 최댓값을 앞으로 땡기자는 생각이었다. 하지만 그렇게 했을 때 코드가 좀.. 여러가지 예외를 처리해 주면서 더러워졌을 뿐만 아니라, 잡지 못하는 예외 상황이 있었다. 그건 바로 숫자를 상호 “교환”하는 것이기 때문에, 최대인 수가 여러 개인 경우에 어떤 수와 교환할 지에 대한 문제였다. 이런 저런 문제와, 틀렸습니다 라는 문구, 그리고 질문 게시..

4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 문제 읽기 일단 처음 읽었을 때는 비트마스킹을 쓰는 문제인가? 싶었다. 맵의 크기가 20x20으로 작긴 하지만, 같은 칸을 여러 번 방문할 수 있다는 조건이 있었기 때문에, 큐에 visited를 계속 넣으면 잘못하면 메모리초과가 날 수도 있다고 생각했다. 그런데 비트마스킹을 어떻게 하는지 잘 생각이 안 나서 일단 다른 방법을 또 생각했다. 두 번째로 생각한 건, 더러운 곳을 각각 하나의 노드로 보고, 로봇 청소기(시작 위치)와 더러운 곳 사이의 거리, 그리고 노드간 거리..