나의 개발일지

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

문제 : https://www.acmicpc.net/problem/2667 🔑 BFS 지도를 돌면서 1을 만나면 bfs 실행한다. 방문했으면 지도에 1을 0으로 바꾼다. 이때 집의 수도 같이 센다. 연결된 단지를 모두 탐색했으면 bfs 종료되고 단지 수를 올린다. from collections import deque n = int(input()) danji = [list(map(int, input())) for _ in range(n)] total_danji = 0 danji_list = [] def bfs(i, j): mx, my = [0, 0, 1, -1], [1, -1, 0, 0] q = deque([(i, j)]) danji[i][j] = 0 cnt = 1 while q: x, y = q.popl..

문제 : https://www.acmicpc.net/problem/16173 BFS 한 칸씩 이동이 아닌 현재 위치에 적혀있는 숫자만큼 이동을 시키는 문제 (오른쪽, 아래로만) from collections import deque n = int(input()) Map = [list(map(int, input().split())) for _ in range(n)] visit = [[0] * n for _ in range(n)] visit[0][0] = 1 q = deque([(0, 0)]) while q: x, y = q.popleft() mx, my = [0, Map[x][y]], [Map[x][y], 0] # 현재 위치에 적힌 숫자만큼 이동 if x == n-1 and y == n-1: print("H..

문제 : https://www.acmicpc.net/problem/9205 BFS (너비 우선 탐색) from collections import deque t = int(input()) def bfs(): n = int(input()) # 편의점 개수 homeX, homeY = map(int, input().split()) # 상근이 집 li = [] # 좌표 리스트 ck = [0] * (n+1) # 체크 리스트 for i in range(n): # 편의점 좌표 입력 받고 리스트에 추가 li.append(list(map(int, input().split()))) endX, endY = map(int, input().split()) # 페스티벌장 좌표 li.append([endX, endY]) # 페스티벌..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844 BFS(너비 우선 탐색)으로 구현 from collections import deque def solution(maps): # 상,하 좌,우 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] q = deque([(0, 0)]) # 시작 좌표 visit = [[0] * len(maps[0]) for _ in range(len(maps))] # 방문 및 이동횟수 체크 리스트 visit[0][0] = 1 # 방문 및 이동횟수 체크 maps[0][0] = 0# 출발지에서 이동한 후에 다시 출발지로 못 오게 하기 위해 0으로 세팅 while q: # q가 빌 때까지 계속 x,..