[Algorithm] 백준 4485 녹색 옷 입은 애가 젤다지? | 파이썬 (다익스트라)
※ 4485 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485 문제 해결 TIP다익스트라를 2차원 배열 형태에 적용해보자. 전체 코드import heapq# 방향 설정: 상, 하, 좌, 우dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def dijkstra(n, graph): # 비용 테이블을 무한대로 초기화 distance = [[float('inf')] * n for _ in range(n)] distance[0][0] = graph[0][0] # 우선순위 큐에 시작점 넣기 (비용, 좌표) queue = [(graph[0][0], 0, 0)] while queue: dist, x, y = heap..
2024. 9. 11.
[Algorithm] 백준 1261 알고스팟 | 파이썬 BFS
※ 1261 알고스팟https://www.acmicpc.net/problem/1261 문제 해결 TIP이전 미로만들기와 동일한 문제이다. n, m 값의 범위만 재설정해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * m for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + ..
2024. 9. 11.
[Algorithm] 백준 2665 미로만들기 | 파이썬 BFS
※ 2665 미로만들기https://www.acmicpc.net/problem/2665 문제 해결 TIPvisited 배열에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 저장한다. bfs로 탐색하면서, 흰 방인 경우를 먼저 탐색한다.(appendleft) 검은 방일 경우에는 이전 visited값에 1을 추가해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * n for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.p..
2024. 9. 11.
