전체 글

헤헤... 백트래킹이 아직 부족한거 같아서 백트래킹 풀기!!!   푼 날짜 : 2024.12.05푼 문제 : [14620] / 꽃길사용한 언어 : python알고리즘 : 브루트포스, 백트래킹  접근방식 :백트래킹을 통해 전수조사를 진행한다. 이 때 범위 자체가 작게 들어오기 때문에 시간초과는 걱정하지 않아도 된다. 꽃을 3개 심을 때마다 각 비용을 카운트 해서 정답 값을 더 작은 값으로 업데이트 했다.  코드 :import sysDIR = 4input = sys.stdin.readlineN = int(input())graph = []for _ in range(N): lst = list(map(int, input().split())) graph.append(lst)visited = [[0 for..

푼 날짜 : 2024.12.04푼 문제 : [26169] / 세 번 이내에 사과를 먹자사용한 언어 : python알고리즘 : DFS, 백트래킹  접근방식 :조건은 "세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력"이다.백트래킹 방식으로 풀이했다.  코드 :import sysinput = sys.stdin.readlineNUM = 5dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]# 정답 확인을 위한 0, 1 체크용 변수check = 0# py, px -> 시작위치, cnt -> 사과 개수 확인, now -> 이동 횟수 확인def backtracking(graph, visited, py, px, cnt, now): global chec..

푼 날짜 : 2024.11.20푼 문제 : [2665] / 미로만들기사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :4방향 탐색을 하며 최소로 방을 변경하는 횟수를 누적해 주었다.이 문제에서는 1이 흰방, 0이 검은 방인데 검은방-> 흰방을 계산해야 해서 0과 1을 바꿔주는 작업이 필요했다. now_color = 0 if int(graph[ny][nx]) else 1all_cost = now_cost + now_color 따라서 위 처럼 현재 컬러에 따라 0인지 1인지 바꾸어서 누적값을 계산했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")dy = [-1, 1, 0, 0]dx = [0, 0..

푼 날짜 : 2024.11.19푼 문제 : [4485] / 녹색 옷 입은 애가 젤다지?사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :N이 0일 때까지 반복하므로 while True에서 N 값에 따라 break를 넣어주었다. 현재위치가 x, y 일때 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 모두 탐색 가능하므로 4방향 탐색을 진행한다.이때 값이 더 작은 경우 업데이트 해주고 아니라면 넘어간다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]def dijkstra(N, graph): heap = [..

푼 날짜 : 2024.11.14푼 문제 : [17396] / 백도어사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :시야가 있는 곳은 계산하지 않고 넘기는 방식에 일반적인 다익스트라 방식으로 계산했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")N, M = map(int, input().split())ward = list(map(int, input().split()))graph = [[] for _ in range(N)]for _ in range(M): a, b, t = map(int, input().split()) graph[a].append((b, t)) graph[b]...

푼 날짜 : 2024.11.16푼 문제 : [1261] / 알고스팟사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :현재위치가 x, y 일때 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 모두 탐색 가능하므로 4방향 탐색을 진행한다.이때 값이 더 작은 경우 업데이트 해주고 아니라면 넘어간다. 최종 목적지까지 반복하면 벽을 최소한으로 부순 값을 알 수 있다.   코드 :import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = []for _ in range(M): lst = list(sys.stdin.readline().rstrip()) graph.append(lst)..

푼 날짜 : 2024.11.15푼 문제 : [23793] / 두 단계 최단 경로 1사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 : 1) (X -> Y) + (Y -> Z) 계산2) X -> Z 계산 (이때 Y는 지나가면 안된다. ) 따라서 아래와 같이 계산을 해서 답을 구했다. XY = dijkstra(X) # X -> Y 계산YZ = dijkstra(Y) # Y -> Z 계산 XZ = dijkstra(X, True) # X -> Z (Y는 지나가면 안됨) 그리고 답이 INF인 경우 -1을 출력했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")N, M = map(int, input().s..

푼 날짜 : 2024.11.15푼 문제 : [18223] / 민준이와 마산 그리고 건우사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :두 개의 경로를 계산해서 계산 값이 일치한다면 "SAVE HIM" 아니라면 "GOOD BYE"를 출력했다. 1) 민준(1) -> 마산(V)2) 민준(1)-> 건우(P) -> 마산(V)   코드 :import sysimport heapqV, E, P = map(int, sys.stdin.readline().split())graph = [[] for _ in range(V+1)]for _ in range(E): A, B, C = map(int, sys.stdin.readline().split()) graph[A].append((B, ..