BFS
[백준] 13460. 구슬 탈출 2 - Python
[Gold I] https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 조금 복잡했던 BFS 시뮬레이션 문제. 이동 시 빨간 구슬과 파란 구슬이 겹쳤을 때, 각각의 이동 횟수를 계산하여 처리하는 방식이 키포인트. BFS의 visited 처리는 빨간 구슬과 파란 구슬의 좌표를 이용한다. 몇 번째 이동인 지는 visited로 확인할 필요 없음. 자세한 풀이는 코드의 주석을 참고하여 확인하면 쉽게 이해..
[백준] 9328. 열쇠 - Python
[Gold I] https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 시간초과와 메모리 초과를 몇 번 받다가, 이리저리 최적화하여 Accepted 받은 문제. 처음엔 [백준] 1194. 달이 차오른다, 가자. 와 비슷해 보여, 비슷하게 Bitmasking을 이용해 풀이할까 생각했지만, 가능한 열쇠의 개수가 26개이므로, 2^26의 경우의 수를 모두 저장할 수는 없어, 다른 방법을 생각했다. 우선 그래프(지도)의 형태를 입력받을 때, 겉을 빈 공간('..
[백준] 1194. 달이 차오른다, 가자. - Python
[Gold I] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 기본적으로 상하좌우 4방향으로 뻗어 나가는 흔한 BFS 형식으로 풀이하면 된다. 그런데 이제 비트마스킹을 곁들인. 열쇠와 문이 없다면, 각 row와 column, 그러니까 아래 코드에서는 visited[r][c] 2차원 배열만 채우며 진행하면 될 것이다. 그러나 열쇠가 있으므로.. 예를 들어, a열쇠를 가지고 (0,0)에 도달한 경우와, a열쇠가..
[백준] 2638. 치즈 - Python
[Gold III] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 "두 변 이상 치즈 외부 공기와 접촉" 한다는 조건만 잘 처리해 준다면, N, M (5 ≤ N, M ≤ 100) 이기 때문에 나머지는 Brute-Force로 처리해도 해결되는 문제이다. air 2차원 배열을 생성하여, 모든 칸을 순회하며, 외부 공기와 접촉한 공기 칸을 체크한다. 이 때, air 배열의 모든 칸은 1로 초기화하고, 외부와 닿아 있는 공기 칸일 ..
[백준] 16236. 아기 상어 - Python
[Gold III] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 우선 그래프 내에서 가장 가까운 칸을 찾기 때문에, BFS로 풀어야 하는 것은 바로 생각이 났고, N 가장 왼쪽 순으로 나열. return list(sorted(prey, key=lambda x: (x[0], x[1], x[2]))) second = 0 size = 2 eat = 0 while True: r, c = shark M[r][c] = size prey =..
[백준] 17142. 연구소 3 - 파이썬
[Gold III] https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다. 문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.' 그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.' 이것들을 유념하며 문제를 풀어 나가야 한다. 풀이 1 일단 BFS 문제라..
[백준] 1697. 숨바꼭질 - 파이썬
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도에 맞지 않게 굉장히 애를 먹었던 문제. 시간초과 메모리초과 틀렸습니다의 늪에서 허우적거린...^ㅁ^ 풀고 보니 결국 하나를 잘못 생각했다. 풀이 1 [백준] 1463. 1로 만들기 와 비슷하게, DP로 풀 수 있을 것이라 생각했으나, 오답. 아무래도 +1, -1이 둘 다 존재하기 때문에, 수가 계속 커지기만 하는 것은 아니라서, 이런 방식으로 풀이하는 것은 불가능..
[백준] 1389. 케빈 베이컨의 6단계 법칙 - 파이썬
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 BFS로 단순하게 풀이하기에는, BFS의 기본 time complexity가 O(N+E) / O(N^2)이므로, 대충 생각해봐도 O(N^2(N+E)) => O(N^3+E*N^2) 정도, 또는 O(N^4) 정도의 time complexity가 된다. 그렇기에, O(N^3) 정도의 time complexity인 Floyd-Warshall(플로이드-..