본문 바로가기
728x90

그래프64

[python] 백준 16236 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 전형적인 이동문제이기 때문에 bfs 또는 dfs를 써야한다는 느낌이 든다. 먹이감이 가장 가까이, 왼쪽에 있는 순으로 우선순위가 있으므로 우선순위에 맞게 먹이를 잡으러간다. 거리를 기록해야하기 때문에 visited 에 최단 이동 거리를 기록한다. 일정 수준 이상 먹으면 크기가 커지는 것을 고려한다. CODE # 16236 아기상어 from collections import deq.. 2023. 5. 29.
[python] 백준 2157 여행 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제 해결 처음에 다익스트라로 풀려고 했으나 k가 매우 클 수 있는 바람에 시간초과가 났다. 큰 수를 계산해야할 때는 무조건 dp가 된다! 그럼 dp를 어떻게 잡아야할까? 우선 똑같은 출발지에서 도착지점까지 항공로가 여러가지가 있을 수 있기 때문에 graph를 $ n \times n$ 행렬을 만든다음 graph[i][j]의 값읠 i에서.. 2023. 5. 7.
[python] 백준 2623 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 해결 위상정렬의 대표적인 문제이다. 위상정렬이란 사이클이 없는 방향 그래프에 노드 순서를 찾는 알고리즘이다. 앞에 필요한 순서가 없는 것을 indegree=0으로 두고 앞에 노드가 이어져있으면 +1 씩 해서 나중에 시작 가능한 지점부터 돌 때 노드가 연결되서 지나갈 때마다 indegree를 1씩 줄여 indegree=0이 되는 순서대로 출력시키는 문제이다. 만약 사이클이 .. 2023. 5. 2.
[python] 백준 13460 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 해결 삼성 문제의 전형적인 시물레이션 문제 기울면 무조건 한 칸 움직이는 것이 아닌 몇 칸 움직일 수 있다는 점이 다른문제와 다르다. 즉 벽에 막히거나 구멍에 들어가서 상황이 종료될때까지 한 방향으로 계속 움직인다. CODE import sys input = sys.stdin.readline from collections import dequ.. 2023. 4. 30.
728x90