BFS

푼 날짜 : 2024.10.27푼 문제 : [3184] / 양사용한 언어 : python알고리즘 : BFS  접근 방식 :BFS로 방문하지 않은 구간을 하나씩 탐색하며 양의 수와 늑대 수를 센다.비교해서 많은 값들을 누적해서 계산해주었다!  코드 :import sysfrom collections import dequeR, C = map(int, sys.stdin.readline().split())graph_ = []for _ in range(R): row = list(sys.stdin.readline().rstrip()) graph_.append(row)visited = [[0 for _ in range(C)] for _ in range(R)]dx = [-1, 1, 0, 0]dy = [0, 0..

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

푼 날짜 : 2024.10.12푼 문제 : [7569] / 토마토사용한 언어 : python알고리즘 : BFS  접근 방식 :dx = [1, -1, 0, 0, 0, 0]dy = [0, 0, 1, -1, 0, 0]dz = [0, 0, 0, 0, 1, -1] 위 아래 왼쪽 오른쪽 앞 뒤 이렇게 6방향을 처리해줘야 했으므로 위와 같이 구성했다.사실 그렇게 어렵지는 않은 문제라 나머지는 코드의 주석으로 확인하면 좋을 것 같다 !   코드 :import sysfrom collections import dequeM, N, H = map(int, sys.stdin.readline().split())graph_ = [[] for _ in range(H)]for i in range(H): for _ in range..

푼 날짜 : 2024.10.11푼 문제 : [12851] / 숨바꼭질 2사용한 언어 : python알고리즘 : BFS  접근 방식 : 사실 저번에 풀다가 "가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성" 에서 막혔었다.1 21 + 1 => 21 * 2 => 2 요런 테케의 경우 방법이 2가지인데 방문 처리를 해버리는 순간 조건문 안에 안들어가서 고민을 좀 했다. visited[i] == -1 or visited[i] == visited[now] + 1 디버깅 하다가 요렇게 수정하고 바로 통과 !역시 오늘도 하나 배워갑니다..   코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split(..

푼 날짜 : 2024.09.06푼 문제 : [13549] / 숨바꼭질3사용한 언어 : python  푼 방법 :BFS로 접근했다.여기서 이전 문제들과 달랐던 점은 다른 이동은 1초 후 이동, 순간이동을 하는 것은 0초 라는 것! 따라서 계산 순서를 [순간이동(*2칸), -1칸, +1칸] 으로 두고 코드를 작성하였는데 지금 생각해보니 순간이동 가능한 범위(max는 동생의 위치 *2 정도로 잡으면 될 것 같다.)를 먼저 다 계산하고 추후 계산(+1, -1)을 해도 될 것 같다는 생각이 들었다.   코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())dx = ['*', '-', '+']def BFS(vis..

푼 날짜 : 2024.08.18푼 문제 : [1326] / 폴짝폴짝사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다.  어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.    이 부분이 중요한데 앞으로 가든 뒤로 가든 현재 위치의 징검다리의 수의 배수만큼만 이동한다는 거 !예시를 들자면 현재위치가 인덱스 4번이고 4번 징검다리에 쓰여 있는 수가 3이라면,  이렇게 1과 7로 이동할 수 있다.만약 배열이 더 길다면 인덱스 7, 10, 13, 16 .... 이렇게 갈 수 있다!   추가적인 테스트케이스를 첨부해보자면,    마지막 3번 테케는 질문게시판에 다른 분이 올려주신 부분을 손으로 그려봤다.  순서대로 N - 징검다리 수..

푼 날짜 : 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.17푼 문제 : [1697] / 숨바꼭질사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다. 이동 가능한 범위는 현재위치에 +1, -1, *2 였기 때문에 이를 배열로 만들어 반복문을 돌며 확인하도록 했다.나머지 방식은 일반적인 BFS와 동일하다.  코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())px = ['-', '+', '*']def BFS(visited, v): queue = deque([v]) visited[v] = 0 while queue: now = queue.popleft() nx = now ..