Algorithm/Graph188 [파이썬] 백준 16954 : 움직이는 미로탈출 (골드3) [파이썬] 백준 16954 : 움직이는 미로탈출 (골드3) https://www.acmicpc.net/problem/16954 문제 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다. 1초 동안 욱제의 캐릭터가 먼저 .. 2024. 2. 19. [파이썬] 백준 9347 : 울타리 (골드3) [파이썬] 백준 9347 : 울타리 (골드3) https://www.acmicpc.net/problem/9347 문제 준규는 화원을 운영중이다. 준규는 엄청난 가치를 지닌 대마꽃를 M개의 행과 N개의 열을 가진 토지에 경작하는데 진욱이가 자꾸 훔쳐가서 고민에 빠졌다. 준규는 진욱이가 훔쳐가지 못하게 꽃 주변을 울타리로 둘러쌓다. 하지만 시간이 지나면서 울타리 몇개가 부서졌다. 진욱이는 이때를 틈타 다시 꽃을 훔지려고 한다. 아래 보이는 그림은 11행 12열의 화원을 나타낸다. 0은 울타리가 없거나 꽃이 심어져 있는 부분을 나타내고 1은 울타리가 있는 곳을 나타낸다. 화원에 들어 오려면 노란색 부분부터 들어와야 한다. 진욱이가 꽃을 훔치러 화원에 들어왔다. 울타리를 요리조리 피해서 들어가는데 이때 상, 하.. 2024. 2. 18. [파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4) [파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4) 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 문제 풀이 0. 방향성 생각 각 소에서 BFS를 돌려서 도달하지 못하는 소의 수를 카운트한다. 다리가 있는 간선을 이용해야하면 이동하지 않는다. 쌍을 구하는 문제이므로 A->B, B->A 이런식으로 중복으로 카운팅이 된다. 이를 제거하기 위해서 소의 수를 모두 구한 후 2로 나누어주기. 1. 입력 from collections import deque i.. 2024. 1. 29. [파이썬] 백준 1162 : 도로포장 (플레5) [파이썬] 백준 1162 : 도로포장 (플레5) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 풀이 0. 방향성 생각 상태 나누기 + 다익스트라 벽뿌 시리즈에서 벽을 부순 횟수로 상태 나눈 것 처럼, 도로를 포장한 횟수를 힙에 추가적으로 넣어서 풀이. 태그에 DP가 달려있긴 한데 기본적인 발상이 다익이랑 똑같다. 1. 입력 import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() n,m,.. 2023. 12. 25. 이전 1 ··· 24 25 26 27 28 29 30 ··· 47 다음
