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

백준 1707번 이분 그래프 파이썬 문제 링크 - https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 두 개의 그룹으로 노드를 나누고, 하나의 그룹의 노드끼리 연결되지 않도록 해야 한다. 문제를 보자마자 간단한 분리 집합 문제라고 생각했다. 하나의 노드를 기준으로 설정하고, 연결된 노드들을 모두 union 한다. 이 때 같은 부모를 가지는 집합에서 연결된 노드가 있다면 ‘NO’를 출력한다. 하지만 굳이 union을 할 필요 없이 BFS만으로도 간단..

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

백준 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를 실행한다. 방문하지 않은 경우나 이미 방문했지만 현재 부숴야..

백준 13549번 숨바꼭질 3 파이썬 BFS 문제 링크 - https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 당연히 백트래킹이겠거니 생각하고 풀었다. 시간 초과에 재귀 오류까지 났지만 가지치기를 조금 더 효율적으로 바꾸는 시도만 계속해서 반복했다. 결국 BFS로 푸는 것을 보고 시도했다. 백트래킹을 항상 쓰려고 하면 안된다. 똑같은 지점에 방문하는 걸 처리하는 것이 까다롭기 때문이다. 1-1. 백트래킹 풀이(오답..

백준 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개까지만 방문할 수 있다는 점을 고려해서 문제를 접근했다..