개구리의 개발 블로그 개구리의 개발 블로그

백준 9370번 미확인 도착지점 파이썬 문제 링크 - https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 생각지도 못한 곳에서 계속해서 오답이 발생했다. 아마 나처럼 오답을 받고 검색하는 사람들이 꽤 될 것 같은 문제다. 최단 거리를 이동하면서 h→g 경로를 선택하는 경우가 무엇을 의미하는 지 파악하는 것이 중요하다. s→g 까지의 최단거리가 s→h→g 인 경우에 h→g 경로를 선택하게 된다. 반대로 s→h 까지의 최단거리가 s→g→h 인 경..

백준 10282번 해킹 파이썬 문제 링크 - https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 간단한 다익스트라를 통해 해결 가능한 문제다. 방문 표시를 하며 다익스트라를 실행한 후 방문된 노드를 계산하는 작업을 따로 해주면 된다. 이 때 방문된 노드까지 가는 최단 시간 중 가장 큰 값을 갱신한다. 1. 풀이 의존성의 방향은 간선의 방향이다. 시작 노드는 1개로 지정되어 있다. 주어진 시작 노드에서 모든 노드에 대한 최단 경로를 구한다. 방문 표시된..

백준 1162번 도로포장 파이썬, 다익스트라 문제 링크 - https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 주어진 도로에서 최대 K개의 도로의 가중치를 0으로 만들 수 있다. 조합을 사용할까 고민했다. 다익스트라를 이용하여 dist배열을 2차원으로 만들고 도로의 가중치를 0으로 만든 횟수를 저장했다. 1. 풀이 heap에 현재까지 누적 가중치, 0으로 만든 도로의 수, 현재 노드를 넣어준다. 다음 노드를 방문..

백준 1261번 알고스팟 파이썬, BFS, 다익스트라 문제 링크 - https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라 문제 분류에서 찾은 문제였다. 아무리 봐도 BFS로 간단하게 풀 수 있을 것 같아서 그렇게 풀었다. 벽 부수고 이동하기 문제랑 거의 유사하다. 1-1. 풀이 현재 노드에 방문하기 위해서 부숴야하는 벽의 개수를 방문 표시에 저장하며 BFS를 실행한다. 방문하지 않은 경우나 이미 방문했지만 현재 부숴야..

백준 1504번 특정한 다익스트라 파이썬 문제 링크 - https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 특정한 다익스트라 문제다. 1. 풀이 1번 정점에서 N번 정점까지의 최단 경로를 구한다. 이 때 반드시 거쳐야 하는 두 개의 정점이 있다. 해당 정점을 v1,v2라고 하자. 경로의 방향은 1번 정점 → (v1,v2) → N번 정점으로 주어졌으므로 v1을 먼저 방문할 지 ,v2를 먼저 방문할 지만 결..

백준 2412번 암벽 등반 파이썬 문제 출처 - https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 그래프 문제 하나 가볍게 푼다고 생각했는데 예상치 못하게 시간을 많이 소비했다. 알고리즘분석 수업에서 2차원 그래프에서 가장 가까운 두 점의 거리 문제를 다루었던 기억이 났다. 비둘기 집 원리로 접근했는데 이번 문제에서도 한 점에서 최대 25개까지만 방문할 수 있다는 점을 고려해서 문제를 접근했다..

2982번 국왕의 방문 파이썬 출처 - https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 로직은 쉽게 생각할 수 있는 다익스트라 문제였다. 다만 국왕이 도로를 점유하고 있는 상황을 표현하는 방법이 조금 까다로웠다. 메모리를 비효율적으로 사용하더라도 우선 풀어야겠다고 생각했다. 인접 행렬과 인접 리스트를 모두 사용하여 국왕의 위치를 표시했다. 1. 풀이 path[u][v]에 u에서 v로 국왕이 이동을 시작한 시간, 도착한 시간을 저장한다. 양방향 그래프..