나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/159993🔑 두 번의 BFS시작 위치에서 레버까지 BFS레버 위치에서 탈출 위치까지 BFS하나의 BFS 함수에 레버 여부를 매개변수로 두고 레버를 찾는지, 탈출구를 찾는지 구분레버를 못 찾거나, 탈출구를 못 찾으면 -1을 리턴 from collections import dequedef solution(maps): answer = 0 def bfs(start, lever): visit = [[0] * len(maps[0]) for _ in range(len(maps))] dx, dy = [0, 0, 1, -1], [1, -1, 0, 0] ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/154540 🔑 BFS로 연결된 무인도를 탐색 maps를 순회하면서 무인도를 만나면('X'가 아닌 부분) 현재 위치에서 BFS 탐색을 실시 BFS를 시작하는 위치와 연결된 무인도들을 모두 탐색하면서 식량 개수를 카운트하고 'X'로 바꾼다. BFS 종료 시 식량 개수를 리턴 또 maps를 순회하면서 무인도를 찾고 BFS 탐색 반복 from collections import deque def solution(maps): def bfs(x, y): mx, my = [0, 0, 1, -1], [1, -1, 0, 0] q = deque([(x, y)]) food = int(maps[x][y]) maps..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/154538 🔑 BFS 6번 테스트 케이스 계속 통과 안 된 이유 🤬 x == y 일 때 0번 만에 만들 수 있다. 트리를 defaultdict를 사용해 기본 값을 0으로 둔다. 큐에 x를 넣어놓고 bfs를 진행 현재 큐에 있는 값으로 x + n, x * 2, x * 3을 해본다. y를 넘어가면 건너뛰고 아니면 계산된 수에 현재 깊이 +1을 한다. 계산된 수를 큐에 넣는다. bfs 종료 후 tree[y]의 값을 리턴한다. (0이면 -1 리턴) from collections import defaultdict, deque def solution(x, y, n): if x == y: return 0..

문제 : https://www.acmicpc.net/problem/28283 🔑 BFS 보안 시스템이 설치되는 컴퓨터로부터 탐색을 시작한다. 각 컴퓨터까지의 깊이를 방문 배열에 저장한다. 보안 시스템이 각 컴퓨터로 뻗어 나가는 순서 탐색 종료 후, 방문 안 했고 이 컴퓨터에서 훔칠 수 있는 돈이 있는 경우는 -1을 출력 (무한히 훔칠 수 있음) 위 조건에 해당하지 않으면 깊이가 저장된 방문배열에 각 컴퓨터마다 (깊이 * 이 컴퓨터에서 훔칠 수 있는 돈) 계산을 한다. 내림차순으로 정렬해서 가장 많은 돈을 훔친 x개의 합을 구한다. 끝 ✨ from collections import defaultdict, deque import sys input = sys.stdin.readline n, m, x, y = ..

문제 : https://www.acmicpc.net/problem/1600 🔑 BFS 중요한 점 갔던 곳이라도 더 빠르게 갈 수 있다면 가야 한다. 원숭이 이동, 말 이동을 따로 만든다. 큐에 x, y, 이동 횟수, 말 능력 사용 횟수를 넣는다. 초기 상태 = [0, 0, 0, 0] 원숭이 이동은 항상 진행한다. 조건은 범위 체크, 방문 체크, 말 능력 사용 횟수 체크 말처럼 이동은 능력 사용 횟수가 남아 있을 때만 진행한다. 조건은 범위 체크, 방문 체크, 말 능력 사용 횟수 체크 from collections import deque import sys input = sys.stdin.readline k = int(input()) w, h = map(int, input().split()) MAP = [..

문제 : https://school.programmers.co.kr/learn/courses/19344/lessons/242259 🔑 BFS 석유가 있으면 현재 좌표를 가지고 BFS를 호출한다. 석유가 있는 덩어리의 크기를 구한다. (cnt) 덩어리의 열 위치를 저장한다. (lst) 저장한 덩어리 열 위치에 덩어리의 크기를 누적 시킨다. (answer) 누적 시킨 리스트의 최댓값이 답 ✨ from collections import deque def solution(land): answer = [0] * len(land[0]) mx, my = [0, 0, 1, -1], [1, -1, 0, 0] visit = [[0] * len(land[0]) for _ in range(len(land))] def bfs(..

문제 : https://www.acmicpc.net/problem/16954 🔑 BFS 먼저 벽이 내려온 상태를 모두 만들었다. (8 개 이후는 벽이 모두 사라지기 때문에 8 개까지) 이전 맵 상태를 가져와서 벽을 내리는데 이때 리스트가 얕은 복사가 되지 않게 주의 그리고 이동 방향은 제자리, 상하좌우, 대각선 총 9개의 방향 제자리 위치하는 방향(i = 0) 일 때도 큐에 넣을 수 있게 방문 처리를 해제했다. 이것 때문에 79% 에서 막혔다가 위 조건 추가로 문제 해결 현재 깊이에 맞는 벽 상태를 보고 갈 수 있는지 확인 (현재 깊이) 갔다면 벽이 내려오고 나서 벽에 안 부딪히는지 확인 (현재 깊이 + 1) 두 조건 만족하면 큐에 추가 도착지에 도착했거나 깊이가 8 이상이 되면 정답 처리하고 끝 ✨ f..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/169199 🔑 BFS 범위가 끝 또는 'D'를 만날 때까지 이동하는 것만 끝 ✨ from collections import deque def solution(board): answer = 0 start, end = [], [] for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == 'R': # 시작점 찾기 start = [i, j] elif board[i][j] == 'G': # 도착점 찾기 end = [i, j] visit = [[0] * len(board[0]) for _ in range(len(board)..