👨💻📱✍️🎢314 BOJ 5014 - 스타트링크 문제 백준 온라인 저지 - 5014번 풀이 과정 건물의 시작 층과 목표 층이 주어졌으므로 BFS 탐색을 통해 목표 지점에 도달하기 위한 최단 경로를 찾으면 됩니다. 층이 건물을 벗어나는 경우만 주의한다면 무난하게 풀 수 있는 문제입니다. 코드 import sys from collections import deque F, S, G, U, D = list(map(int, sys.stdin.readline().split())) def bfs(start): visit = [0 for _ in range(F+1)] q = deque() visit[start] = 1 q.append((start, 0)) while q: here, cost = q.popleft() if here == G: return cost fo.. 2021. 6. 9. BOJ 1389 - 케빈 베이컨의 6단계 법칙 문제 백준 온라인 저지 - 1389번 풀이 과정 찬구 관계를 그래프로 표현하면 케빈 베이컨의 수가 한 정점으로부터 다른 모든 정점까지의 최단 거리의 합이라는 것을 알 수 있습니다. 따라서 플로이드 와샬 알고리즘 을 활용해 모든 정점간의 최단 거리를 구한 뒤 케빈 베이컨의 수가 가장 작은 사람을 찾는 방법으로 해결했습니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) adj = [[sys.maxsize] * N for _ in range(N)] for _ in range(M): frm, to = list(map(int, sys.stdin.readline().split())) adj[frm-1][to-1] = 1 adj[to-1][fr.. 2021. 6. 9. BOJ 2644 - 촌수계산 문제 백준 온라인 저지 - 2644번 풀이 과정 문제 조건을 통해 각 자식은 오직 하나의 부모만 주어지므로 사이클 없는 무방향 그래프로 나타낼 수 있습니다. 따라서 촌수를 계산하고 싶은 두 사람중 임의로 한명을 선택한 뒤 다른 한명에 도달하는 거리를 계산하면 답을 구할 수 있습니다. 이때, 도달 가능성 유무는 DFS 를 통해 계산된 거리값을 통해 알 수 있도록 하였습니다. 코드 import sys n = int(input()) target = list(map(int, sys.stdin.readline().split())) m = int(input()) adj = [[] for _ in range(n+1)] for _ in range(m): frm, to = list(map(int, sys.stdin.re.. 2021. 6. 9. BOJ 10026 - 적록색약 문제 백준 온라인 저지 - 10026번 풀이 과정 입력된 board 의 크기가 크지 않으므로 DFS 탐색을 통해 모든 구간을 찾아줬습니다. 색맹이 있는 사람과 없는 사람은 탐색 제약조건이 다르기 때문에 각각 visit 배열을 만들어서 따로 탐색을 수행했습니다. 2번의 DFS 를 수행해도 총 시간 복잡도가 O(2n) 이기 때문에 시간 내에 수행이 가능했습니다. 코드 import sys sys.setrecursionlimit(10**6) N = int(input()) board = [] for _ in range(N): board.append(list(sys.stdin.readline()[:-1])) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def dfs(x, y, visit, d.. 2021. 6. 9. BOJ 3135 - 라디오 문제 백준 온라인 저지 - 3135번 풀이 과정 라디오의 세 가지 버튼을 이용해서 목표 주파수에 도달하도록 하는 최소 버튼 입력 횟수를 구하는 문제입니다. 주파수의 최소 및 최대 지점이 서로 이어져있지 않기 때문에 단순하게 즐겨찾기 목록들의 주파수들과의 차이값과 A 에서 B 까지의 차이값 중 가장 작은 값을 찾으면 됩니다. 코드 import sys def solution(): min_value = 2e9 for freq in frequency: min_value = min(min_value, abs(freq - B)) return min(min_value + 1, abs(A - B)) if __name__ == '__main__': A, B = list(map(int, sys.stdin.r.. 2021. 6. 9. BOJ 13410 - 거꾸로 구구단 문제 백준 온라인 저지 - 13410번 풀이 과정 구구단을 수행하되 그 결과를 뒤집었을 때의 최대 값을 구하는 문제입니다. 요구조건이 복잡하지 않고 입력값도 크지 않기 때문에 완전 탐색을 통해 답을 구할 수 있습니다. 코드 import sys def solution(N, K): max_value = 0 for i in range(1, K + 1): num = str(N * i)[::-1] max_value = max(max_value, int(num)) return max_value if __name__ == '__main__': N, K = list(map(int, sys.stdin.readline().split())) answer = solution(N, K) print(answer) 2021. 6. 8. 이전 1 ··· 17 18 19 20 21 22 23 ··· 53 다음
