https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 문제에 대한 자세한 내용은 백준에서 참고해주세요 풀이 1. 택시 운전자는 가장 가까운 거리에 있는 고객을 먼저 태워야 합니다. (만일 같은 거리에 존재하는 고객이 여러 명이라면 최소 행 위치에 있는 고객을 태우며, 같은 행에 존재하는 고객이 여러 명이라면 최소 열 위치에 있는 고객을 태운다) 이 때 정렬이 필요함을 알 수 있습니다. 2. 택시 운전자의 ..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 BFS알고리즘을 적용해서 주어진 S초가 지난 뒤에 갱신된 grid에서 목표 값을 출력해준다. 코드 # 18405번 경쟁적 전염 import sys from collections import deque n, k = map(int, sys.stdin.readline().split()) grid = [] queue = [] for i in range(n): li = ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS 알고리즘을 사용해서 문제를 풀어주었습니다. 3차원 리스트이기에 주의해서 짜주시면 됩니다. 코드 # 6593번 상범 빌딩 import sys from collections import deque dxyzs = ((0,0,1), (0,0,-1), (1,0,0), (-1,0,0), (0,1,0), (0,-1,0)) while True: L, R, C = map(int, sys.stdin.read..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 BFS 알고리즘을 이용하여서 문제를 풀어주면 됩니다. 단순한 알고리즘 구현이 가능하다면 무리없는 문제입니다. 코드 # 2636번 치즈 import sys from collections import deque input = sys.stdin.readline m, n = map(int, input().split()) grid = [list(map(int, input().split())) for _ in ..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 bfs를 이용하여서 문제를 풀어주었습니다. 코드 # 16953번 A → B from collections import deque a, b = map(int, input().split()) def bfs(): queue = deque([]) queue.append([0, a]) while queue: cnt, c_a = queue.popleft() if c_a < b: queue.append([cnt+1, c_a*2]) queue.append([cnt+1, int(str(c_a)+"1")]) if c_a == b: r..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이(BFS 풀이) 기존의 BFS문제와 같이 BFS로 주어진 동굴을 탐색할 것입니다. 파이썬에서는 BFS를 사용할 경우 deque를 이용해줍니다.이 deque에 다음 좌표를 집어넣는 조건을 다음과 같이 설정하였습니다. 기존의 저장된 루피 값보다 현재의 루피 값이 작을 경우에만 deque에 좌표를 넣어주었습니다. 모든 좌표가 최소 루피 값을 가질 경우에 BFS함수가 종료됩니다. #..

https://www.acmicpc.net/problem/16469 16469번: 소년 점프 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 www.acmicpc.net 풀이 스윙스, 넉살, 창모가 모이는데 최소 경과 시간과 그러한 지점들의 개수를 출력해주는 것이 목표입니다. # 16469번 소년 점프 import sys from collections import deque input = sys.stdin.readline # 좌표 dxs = [0, 0, 1, -1] dys = [1, -1, 0, 0] # row 행, col 열 row, col ..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 # 18352번 특정 거리의 도시 찾기 import sys import heapq INF = sys.maxsize def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = he..