개발야옹

✅ 정답 코드# 유기농 배추from sys import stdinfrom collections import dequeinput = stdin.readlinedef get_position(): for i in range(N): for j in range(M): if ground[i][j] == 1: return (i, j) return (-1, -1)def bfs(value): global ground start = get_position() queue = deque([start]) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: x, y..

🎲 주사위 굴리기시간 제한: 2초메모리 제한: 512MB📄 문제크기가 N x M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다.주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여저 있는 곳의 좌표는(x, y)이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있..

🌼 이전 내용다익스트라 알고리즘 이론 및 구현 코드플로이드 워셜 알고리즘 이론 및 구현 코드🌼 최단 경로 알고리즘 기초 문제 풀이📄 전보: 문제 설명어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다.하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도..

🌼 Floyd-Warshall Algorithm (플로이드 워셜 알고리즘)🌼 플로이드 워셜 알고리즘모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.다만, 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.플로이드 워셜 알고리즘은 DP 유형에 속한다.각 단계마다 특정한 노드 K를 거쳐가는 경로를 확인한다.a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 좋은지 검사점화식Dab = min(Dab, Dak + Dkb)?..