문제https://www.acmicpc.net/problem/9205 풀이코드# 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.# 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.from collections import dequedef bfs(): que = deque() que.append((home_idx_x,home_idx_y)) while que: x,y = que.popleft() if ab..
Algorithm/baekjoon
문제https://www.acmicpc.net/problem/5567 풀이코드 from collections import dequedef bfs(start_num,depth): global answer que = deque() que.append((start_num,depth)) while que: start_num,depth = que.popleft() visited_list[start_num] = True for i in linked_list[start_num]: if visited_list[i] != True and depth 문제접근친구관계를 저장하기 위해 linked_list 를 사용하여 친구관계를 저장한다. 이때 a..
문제https://www.acmicpc.net/problem/17070 풀이 코드1(실패) (BFS탐색) from collections import dequen = int(input())mapp = [list(map(int, input().split())) for _ in range(n)]dx = [1, 1, 0] # 가로, 대각선, 세로 이동dy = [0, 1, 1]now = [0, 1, 2] # 0: 가로, 1: 대각선, 2: 세로dp = [[[0] * 3 for _ in range(n)] for _ in range(n)] # dp[y][x][방향] = 경로 개수 저장dp[0][1][0] = 1 # 처음 파이프 위치: (0,1)에서 가로로 시작que = deque([[0, 1, 0]]) # ..
문제https://www.acmicpc.net/problem/4179풀이 코드from collections import dequeimport sys# J와 F동시에 BFS시작# 탐색한 좌표를 담을 수 있는 변수 x 필요 # 해당 변수에 J와 F를 구분할 수 있는 변수 필요# 좌표를 담은 변수x를 pop하며 탐색 진행# 탐색을 한 후, 다시 x에 저장, 이때 카운티 1증가# J가 F랑 곂치면 임파서블 출력# J가 벽 외각에 도달하면 cnt 출력r,c = map(int,input().split())dx = [-1,1,0,0]dy = [0,0,-1,1]answer = "IMPOSSIBLE"def bfs(): global answer while que: # print(mapp) ..
문제 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 풀이 코드 # 다음과 같은 우선순위를 차례로 적용하여 만들어진다. # # 자주 나오는 단어일수록 앞에 배치한다. # 해당 단어의 길이가 길수록 앞에 배치한다. # 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 # # M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다..
문제 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 코드 풀이 import heapq n,m = map(int,input().split()) INF = int(1e9) linked_list = [[] for _ in range(n+1)] for i in range(m): node1,node2,cost = map(int,input().split()) linked_list[node1].append((node2,cost)) linked_list[node2].append((node1,cost)) distance = [INF..
문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 코드 풀이 import sys from itertools import combinations from collections import deque input = sys.stdin.readline # def bfs(list1): # start_node = list1[0] # que = deque() # que.append(start_node) # visited = [] # visited.append(start_node) # sum1 = 0 # while que: # node = q..
문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 풀이 # 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. # 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. # 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. # 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다. ..
문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 코드 풀이 import copy import sys sys.setrecursionlimit(10**6) n = int(input()) n_dice = [] total_dice = [] depth =0 summ_dice = 0 for i in range(n): n_dice.append(list(map(int,input().split()))) def sum_dice(idx,depth): global ..
