개발하는 사막여우

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): min_dis = [int(1e9)] *(n+1) q = [] hq.heappush(q,[0,start]) min_dis[start] = 0 while q: cur_dis,cur_node = hq.heappop(q) if min_dis[cur_node..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 소스코드 풀이 ★ b가 감염되면 s초 이후 a가 감염되는 형태이기 때문에 그래프를 만들 때 b -> a로 향하는 간선을 만들어줘야 합니다 ! ★ 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력해주는데, 감염이 이루어질 때마다 이전에 걸렸던 시간과 비교하여 최댓값을 찾아줍니다. ★ 기존에 min_dis 배열을 int(1e9)로 초기화 해뒀기 때문에 감염되지 않은 컴퓨터들은 int(1e9)가 값이고, 감..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 소스코드 풀이 ★ 주어진 두 정점을 반드시 거치면서 최단 경로로 이동해야 하기 때문에 1부터 n까지 이동할 수 있는 방법은 총 두가지입니다. 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 위 두 케이스를 통해 경로를 도출하고, 그 중 최단경로를 출력해줍니다 :)

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 소스코드 풀이 ★ 벽을 부숴야 하는 경우, 최소로 부수면서 목표지점에 도달해야 하기 때 힙 큐 안에 벽을 깬 횟수를 기준으로 최소정렬을 해줍니다 ! 그럴 경우 벽을 깬 경우는, wall 변수에 1씩 추가해주고, 깨지 않은 경우는 wall을 그대로 큐에 넣어줍니다. 이렇게 되면, 벽을 깬 횟수가 작은 좌표부터 상하좌우 탐색을 하게 되고 목표지점까지 도달할 수 있는지 확인하게 됩..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 소스코드 풀이 ★ 다익스트라를 구현하는 과정을 전형적인 과정과 똑같습니다. 다만 목표인 마을로 가는 최단거리와 다시 돌아오는 최단거리가 다를 수 있기 때문에 두 과정 모두에 최단거리를 도출해야 합니다. 그 후 가장 많은 시간을 소비하는 학생을 찾아주면 됩니다 :)

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 소스코드 풀이 ★ 잃을 수밖에 없는 금액을 최소한으로 하여 n-1,n-1까지 찾아가는 전형적인 다익스트라 문제입니다 ! 최소 금액을 저장하는 배열인 min_c를 이차원 배열로 만들어 각각의 좌표마다 금액의 크기를 확인해줘야 합니다.

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 소스코드 import sys from collections import deque input = sys.stdin.readline nx = [-1,0,1,0] ny = [0,1,0,-1] def BFS(a,b): dq = deque() dq.append([a,b,0]) visited[a][b] = True while dq: x,y,life = dq.popleft() if x ..

https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 소스코드 풀이 ★ 주어진 조건에 부합하지 않을 경우 어떻게 방을 생성해줄지에 대해 조금 생각했던 문제였습니다 ! ★ 자세한 부분은 주석을 참고하시면 될 거 같습니당 :)

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 소스코드 풀이 ★ 입력으로 키가 1인 사람부터 n인 사람까지 자신보다 앞에 있으면서, 키가 더 큰 사람의 수가 주어집니다 ! 그렇기에 키가 가장 큰 사람부터 자신 앞에 몇명이 존재하는지를 생각해보면 됩니다. 이때 insert() 함수를 사용하게 되는데, insert함수 insert(a,b)는 인덱스 번호 a자리에 b를 삽입시키는 기능을 가지고 있습니다. ★ 입력을 예시로 들었을 때, 2 1..

https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 소스코드