본문 바로가기

Algorithm/BOJ133

[백준] 3584번 - 가장 가까운 공통 조상 (파이썬) # 가장 가까운 공통 조상 def find_parent(parent, x): result = [x] while parent[x]: result.append(parent[x]) x = parent[x] return result T = int(input()) for _ in range(T): N = int(input()) parent = [0 for _ in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) parent[b] = a x, y = map(int, input().split()) # 각 부모 리스트 정의 x_parent = find_parent(parent, x) y_parent = find_parent(parent, y) # 깊.. 2022. 5. 1.
[백준] 16197번 - 두 동전 (파이썬) # 두 동전 import copy from collections import deque N, M = map(int, input().split()) arr = [] money = deque() for i in range(N): arr.append(list(input().strip())) for j in range(M): if arr[i][j] == 'o': money.append((i, j)) arr[i][j] = '.' visited = set() visited.add(''.join(map(str, money))) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def bfs(): q = deque() q.append((0, money)) while q: cnt, now = q.pop.. 2022. 4. 20.
[백준] 16916번 - 부분 문자열 (파이썬) # 부분 문자열 P, S = input().strip(), input().strip() def get_table(x): arr = [0 for _ in range(len(x))] j = 0 for i in range(1, len(x)): while j > 0 and x[i] != x[j]: j = arr[j-1] if x[i] == x[j]: j += 1 arr[i] = j return arr def kmp(word, find): result = 0 j = 0 for i in range(len(word)): while j > 0 and word[i] != find[j]: j = table[j-1] if word[i] == find[j]: if j == len(find)-1: result += 1 j = .. 2022. 4. 18.
[백준] 2234번 - 성곽 (파이썬) # 성곽 import sys from collections import deque from collections import defaultdict input = sys.stdin.readline M, N = map(int, input().split()) arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) # 방향은 8,4,2,1 순서로 남,동,북,서 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] def bfs(a, b, arr, visited, room_num): q = deque() q.append((a, b)) visited[a][b] = room_num room_size = 1 while q: x, y.. 2022. 4. 17.
[백준] 24042번 - 횡단보도 (파이썬) # 횡단보도 import heapq import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [[] for _ in range(N+1)] for i in range(M): a, b = map(int, input().split()) arr[a].append((i, b)) arr[b].append((i, a)) def dijkstra(): q = [] heapq.heappush(q, (0, 1)) visited = [sys.maxsize for _ in range(N+1)] visited[1] = 0 while q: time, node = heapq.heappop(q) if node == N: return time if visi.. 2022. 4. 16.
[백준] 24041번 - 성싶당 밀키트 (파이썬) # 성싶당 밀키트 import sys from collections import defaultdict input = sys.stdin.readline N, G, K = map(int, input().split()) info = defaultdict(list) for _ in range(N): speed, limit, isImportant = map(int, input().split()) info[isImportant].append((speed, limit)) def get_g(x, k): result = 0 for speed, limit in info[0]: result += speed*max(1, x-limit) info[1].sort(key=lambda k: -k[0]*max(1, x-k[1])) f.. 2022. 4. 15.
[백준] 1726번 - 로봇 (파이썬) # 로봇 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] sa, sb, sd = map(int, input().split()) ea, eb, ed = map(int, input().split()) dx = [0, 0, 0, 1, -1] dy = [0, 1, -1, 0, 0] def bfs(): q = deque() q.append((0, sa-1, sb-1, sd)) visited = [[[False for _ in range(5)] for _ in range(M)] fo.. 2022. 4. 13.

티스토리툴바