본문 바로가기

그래프 탐색

 (41)
[Python] 5427번 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 22/11/20 전형적인 BFS문제로, 아이디어 하나만 떠올리면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 일반적인 BFS문제 같은 경우는, 시작점이 하나만 주어져서 그냥 하면 되는데, 이 문제 같은 경우, 불도 상근이처럼 네 방향으로 퍼진다고 했으므로, 불도 시작점에 넣고 BFS를 돌려주어야 한다. 이때, 불과 상근이는 당연히 따로따로 처리해줘야한다. 불과 상근이를 시작점으로 맨 처음에 넣을 때 유의해야..
[Python] 1584번 게임 https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 22/11/20 전형적인 그래프 탐색 문제로, 간선의 가중치 정보가 0과 1밖에 없기 때문에 다익스트라 대신 0-1 BFS로 풀어도 무방한 문제이다. 2022.09.02 - [백준 문제 풀이] - [Python] 13549번 숨바꼭질 3 (추후 보강 예정) [Python] 13549번 숨바꼭질 3 (추후 보강 예정) https://www.acmicpc.net/problem/1..
[Python] 1707번 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 22/11/14 전형적인 BFS, DFS응용 문제로, 이분 그래프에 대한 정의를 잘 알고 있기만 한다면 쉽게 풀 수 있는 문제이다. 이 문제에서는 BFS로 접근했으며, DFS로는 조금 귀찮을 것 같아 DFS로는 접근하지 않았다. 의외로 조금씩 틀렸었던 문제로, 문제를 잘 읽는 습관을 기르도록 하자. 문제 접근 방식: 처음에는 이분 그래프의 정의를 헷갈려서 틀렸습니다를 받았다. 어떤 식으로 이해했었..
[구름 알고리즘 먼데이 챌린지] 3주차 4번 순환하는 수로 22/11/07 DFS/BFS 문제로, 사이클을 출력하는 문제이다. 문제 접근 방식: 사실 이 문제의 해설보다 더 간단한 방법으로 나는 풀었다. 심지어 BFS, DFS도 돌리지 않았다. 나는 문제 조건의 핵심을 꿰뚫어봤다. 먼저, 문제 조건을 보면, 사이클은 단 하나만 존재한다고 했다. 때문에, 노드들과 간선들이 주어져 있으면, 노드들 중에 간선이 하나만 연결되어 있는 노드들은 사이클을 이루고 있지 않다고 생각했다. 왜냐하면, 그 노드가 사이클에 포함되어있다면, 그 노드는 최소 2개 이상의 간선에 연결되어 있기 때문이다. 이러한 이유로, 사이클을 이루고 있지 않은 노드는 그 간선과 노드를 그래프에서 제거해버렸다. 이 과정을 계속 반복하다보면 결국 사이클 하나만 남게 되는데, 이것을 오름차순으로 출력하면 ..
[Python] 5011번 Robots on a grid https://www.acmicpc.net/problem/5011 5011번: Robots on a grid You have recently made a grid traversing robot that can find its way from the top left corner of a grid to the bottom right corner. However, you had forgotten all your AI programming skills, so you only programmed your robot to go rightwards and downwards www.acmicpc.net 22/10/14 전형적인 BFS문제에 갈 수 있는 방법을 구하는 DP문제가 더해진 문제로, 개인적으로 골드 5가 적당..
[Python] 16958번 텔레포트 https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 22/10/27 다양한 풀이가 존재하는 문제로, 파이썬으로 풀기 위해서는 별의별 최적화를 다 해야 되는 문제이다. 나이브한 플로이드-워셜 알고리즘으로 접근한다면 파이썬에서는 TLE를 받을 수밖에 없기 때문에 무조건적인 최적화가 필요하다. 이 글에서는 2가지 풀이 방법을 소개할 것이다. 첫 번째 문제 접근 방식: 이 문제를 먼저 접했을 때, 도시의 수의 ..
[Python] 17114번 하이퍼 토마토 https://www.acmicpc.net/problem/17114 17114번: 하이퍼 토마토 첫 줄에는 문제의 설명에서 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 106 이다. 둘째 줄부터는 창고에 저장된 토마토들의 정보가 주어진다. 창 www.acmicpc.net 22/10/11 기존 토마토 문제(7576번, 7569번)와 기본적인 접근 방법 자체는 똑같다. 하지만, 11차원으로 인해 생기는 시간 부족을 관리해야 되기 때문에 약간 코드가 다르게 적을 수밖에 없었다. 2022.09.20 - [백준 문제 풀이] - [Python] 7576번 토마토 [Python] 7576번 토마토 7576번: 토마토 (acm..
[Python] 14496번 그대, 그머가 되어 https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 22/10/08 단순 BFS문제이다. 문제 접근 방식: 이 문제에서 요구하는 바는 a를 b로 바꾸기 위해 필요한 최소 치환 횟수이다. 결국 어느 정점에서 다른 한 정점으로 가는 최소 거리를 구하는 문제와 별 다를 바가 없으므로, BFS로 해결할 수 있다. 구현하는데 주의할 점은 행렬과 같이 주어진 그래프와는 다르게 실제 간선으로 그래프가 주어져서, 그 ..

티스토리툴바