Koo's.Co

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 위상 정렬과 dp를 이용해 풀 수 있는 문제입니다. ACM Craft 문제와 거의 동일한 문제인 것 같습니다. 먼저 위상 정렬을 이용해 각 값들의 진입 차수를 구해준 후 bfs를 사용했습니다. 작업을 하기 위해서는 선행 작업들을 모두 수행해야 하기 때문에 dp리스트를 만들어 이전 작업들 중 가장 시간이 오래 걸린 값들만 저장해줍니다. -> max를 이용해 노드에 한 번 도착할 때마다 값을 갱신! 모든 작업이 완료된 시간을 구해야하기 때문에 max를..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 bfs를 사용해서 푸는 문제입니다. 문제의 조건이 많은데 하나씩 살펴보며 풀어보겠습니다. 상하좌우 이동 가능 -> directions = [(-1, 0), (0, -1), (1, 0), (0, 1)] 상어와 물고기는 크기를 갖고 있음 처음 상어 크기 = 2 -> shark_size = 2 물고기의 크기 = 1 ~ 6 상어보다 "작은" 물고기만 먹을 수 있다 상어와 크기가 "같은" 물고기는 지나갈 수 있다 상어보다 크기가 "큰" 물고기는 지나갈 수 없다..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 전에 풀었던 연구소 문제와 비슷하다 생각하여 백트래킹 방법을 먼저 생각해봤다. 연구소 문제는 주어지는 맵의 크기가 최대 8 x 8인 64였는데 이 문제는 최대 크기가 1,000 x 1,000으로 bfs를 사용해서 풀 경우 시간 복잡도가 O(NM^2)이 되는 절대 풀 수 없는 문제였다^^ import sys from collections import deque read = sys.stdin.readline direction = [(-..

max_depth: max_depth = len(visited) res = [i] elif len(visited) == max_depth: res.append(i) in 연산자를 사용해 방문 노드를 탐색하는게 시간이 오래 걸리는 것 같아 리스트에 방문 노드를 추가한 후 길이를 확인하는 방식이 아니라 bool 리스트를 만들어서 방문 노드를 True로 바꾸는 방식으로 바꿔 풀었다. import sys from collections import deque read = sys.stdin.readline def MIS(): return map(int, read().split()) n, m = MIS() graph = [[] for _ in range(n + 1)] for _ in range(m): e, s = M..

21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 풀이 기존 bfs 문제와 동일하지만 픽셀이 3개의 원소로 이루어져 있다는 점에 차이가 있다. 동일하게 이중 리스트로 입력을 받은 후 리스트를 3칸씩 뛰어서 3개의 픽셀값들을 평균내었다. 값을 255로 바꿔주지 않고 visited 리스트를 별도로 만들어주었는데 그냥 값들을 255로 바꿔주고 이걸로 방문여부를 판단했어도 될 것 같다. import sys from collections import deque read ..

5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 2차원 리스트로 친구들의 관계 그래프를 표현하였다. bfs를 한 후 거리가 1 ~ 2인 친구들의 수만 구하면 친구와 친구의 친구 수를 구할 수 있다. import sys from collections import deque read = sys.stdin.readline n = int(read()) L = [[] for _ in range(n + 1)] dist = [0] * (n + 1) for _ in range(int(read())): s..

1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 탐색 알고리즘은 기존 문제들과 동일하게 적용하여 풀었다. 이 때 B와 W 각각의 개수를 세서 제곱을 해주어야 하기 때문에 bfs 함수를 호출할 때 색상에 대한 정보도 같이 파라미터로 넘겨주었다. import sys from collections import deque read = sys.stdin.readline directions = [(-1, 0), (0, -1), (1, 0), (0, 1)] def bfs(i, j, c): q..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 일반적인 bfs와 동일하게 풀 수 있다. 조금 다른 아이디어가 있다면 기존 bfs 문제들은 하나의 시작점을 큐에 넣고 시작하는데 여기서는 먼저 전체 graph를 순회한 후 해당하는 시작점을 모두 큐에 넣고 시작한다는 점이다. 다른 점은 기존 bfs 문제와 동일하다. import sys from collections import deque read = sys.stdin.readline directions = [(-1, 0), (0, -1), ..