BFS11 [Python] 16234. 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net Point 시작점을 기준으로 bfs를 통해 연합국가의 좌표를 탐색하고, 평균을 연산한다. 실제 값 반영은 이동에서 수행한다. Tip bfs의 세번째 반환값으로 flag를 세워서 인구이동이 필요없는(길이가 1)인 국가를 이동대상에 포함하지 않으므로서 연산량을 대폭 줄인다 check 이차원 배열을 선언해 한번 연합이 탐지된 국가는 모두 True 표시하여 bfs 연산이 필요없도록 한다 메모리 (제한: .. 2021. 4. 24. [Python] 19238. 스타트 택시 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net Point 처음엔 매 승객마다 최단거리를 구해줬고 시간초과가 났다. 그럴 필요 없이 현재 택시 위치 기준으로 맵의 최단거리를 구하고 Pop(index) 를 이용해서 연산을 반복한다. 메모리 (제한: MB) 124568 KB 시간 (제한: 초) 204 ms 결과 100% def shortest_path(taxi): global n dist = [[-1]*n for _ in .. 2021. 4. 23. [Python] 17142. 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 아무리 수정해도 계속 시간초과 됨 ㅠㅠ 다음에 재도전 메모리 (제한: MB) 0 KB 시간 (제한: 초) 0 ms 결과 시간초과 import itertools def bfs(_lst,_dist): global n,answer,vacumm lst = list(_lst) cnt = 0 infected = 0 for i in range(len(lst)): _dist[lst[i][0]][lst[i][1]] = 0 while T.. 2021. 4. 20. [Python]14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 문제를 풀기전에 제약조건을 먼저 확인하고 경우의수를 계산해본다. 3 ≤ N, M ≤ 8 이고 벽은 3개를 배치하므로, N*M Combina.. 2019. 5. 9. [Python]16985. Maaaaaaaaaaze https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다. www.acmicpc.net Step1. 순열 생성 -> 블록이 쌓이는 순서를 생성해준다. 여기서는 5! 경우의 수 Step2. 회전 -> 각 층에 있는 블록은 독립적으로 회전한다. 블록당 4번 회전할 수 있으므로, 4^5 의 경우의 수 Step3. 탐색 -> (0,0,0) 부터 (4,4,4) 까지 BFS탐색으로 최단거리를 리턴한다. 최악일때 5*5*5 3차원 큐브에 있는 1칸짜리 블록은 상하.. 2019. 4. 12. [Python]16236. 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net BFS + 약간의 시뮬레이션 문제라고 생각한다. 누구는 BFS만으로도 푼다. 코드구현은 한시간 걸린듯 한데 디버깅이 너무너무너무 오.. 2019. 4. 9. [Python]3055. 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 물이 미리 차오르는 시간을 구한다음, 고슴도치를 움직이도록 한다. 12345678910111213141516171819202122232425.. 2019. 4. 2. [Python]2206. 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394.. 2019. 4. 2. [Python]1261. 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 이 문제의 경우 주변이 '0' 이면 가중치가 0, 주변이 '1' 이면 가중치가 1이다. 따라서 일반적인 Queue를 사용한 BFS는 절대 풀 수 없고 Deque을 이용해서 가중치가 0 일땐 앞에다 추가하고 가중치가 1일땐 뒤에다가 추가해줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18.. 2019. 4. 2. 이전 1 2 다음 728x90 반응형
