그래프

푼 날짜 : 2024.10.18푼 문제 : [13913] / 숨바꼭질 4사용한 언어 : python알고리즘 : BFS  접근 방식 :가장 빠른 시간을 출력하는 것은 사실 이전과 비슷한 문제이기 때문에 어렵지 않았다.중요한 것은 이동 방법이 여러개인데 이를 어떻게 출력할 것인가 였다! 내가 결정한 방법은1) 이동 방법과 이동했을 때 위치를 저장2) 도착지점에서 세 가지 이동 방식을 활용해서 출발지점으로 이동하는 방법을 찾기 -> stack에 추가3) 출력을 pop을 사용해서 해준다였다. 사실 여러가지 이동 방법 중 하나의 이동 방법만 출력하면 되기에 가능한 시도였던 것 같다.  코드 :from collections import dequeN, K = map(int, input().split())# 방문 처리..

푼 날짜 : 2024.09.011푼 문제 : [1303] / 전쟁 - 전투사용한 언어 : python  푼 방법 :DFS로 접근하였다. N명이 뭉쳐있을 때는 N*N의 위력을 낼 수 있다.  같은 병사가 몇 명이 뭉쳐있는지를 계산하고 그 인원의 제곱을 구한다.우리 병사와 적국 병사의 위력의 총합을 출력한다. 범위 계산과 추가적으로 현재의 target과 일치하면 지속해서 DFS를 실행하고 아니라면 제곱값을 총합에 더하여 다음 과정을 진행하도록 구현했다.  코드 :import sysN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(N)] for _ in range(M)]for _ in range(M): ..

푼 날짜 : 2024.08.17푼 문제 : [16953] / A → B사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다. 처음 풀었을 때 메모리 초과가 났다.아무래도 범위가 최대 10^9 이기 때문에 배열을 다 만든다고 하면... 그래서 생각한 방법이 dictionary다.불필요한 visited를 다 만들어 놓지 말고 필요한 값만 저장하기로 했다.사실 리스트에서 딕셔너리로 변경한 것 말고는 크게 BFS문제를 벗어날 정도의 난이도가 아니었기 때문에 코드는 전반적으로 비슷하다.   코드 :import sysfrom collections import dequeA, B = map(int, sys.stdin.readline().split())visited = {} # 딕셔너리로 만들기px =..

푼 날짜 : 2024.08.16푼 문제 : [14248] / 점프 점프사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다. 한 칸씩 이동하는 다른 문제와 달리 이번 문제는 돌다리의 숫자만큼 좌우로 움직일 수 있으므로 그 숫자를 저장하고 현재 위치에서 빼거나 더하는 방식으로 접근하였다.   코드 :import sysfrom collections import dequeN = int(sys.stdin.readline())graph_ = list(map(int, sys.stdin.readline().split()))graph_.insert(0, 0) # 문제를 편하게 풀기 위해 index 0 추가visited = [0 for _ in range(N+1)]start = int(sys.stdin..

푼 날짜 : 2024.07.25푼 문제 : [14940] / 쉬운 최단거리사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력  처음에는 리스트 형식( [1, 2, 3, ~] )으로 출력을 잘못해서 틀렸고, 두 번째에는 위의 예외처리를 안해줘서 틀렸다.  항상 문제를 꼼꼼하게 읽자!   코드 :import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(M)] for _ in range(N)]dx = [1, -..