동까의 코딩

파이썬 프로그래머스 - 게임 맵 최단거리문제 설명프로그래머스의 게임 맵 최단거리 문제는 직사각형 모양의 맵에서 시작점(0, 0)에서 도착점(n-1, m-1)까지 이동할 때 거쳐야 하는 최소 칸 수를 구하는 문제입니다.맵은 1과 0으로 구성되며, 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타냅니다.상하좌우 방향으로만 이동할 수 있으며, 시작점과 도착점은 항상 1입니다.문제 접근 방식BFS(너비 우선 탐색) 활용시작점에서 출발하여 도착점까지 도달하는 경로 중, 가장 짧은 경로를 찾아내기 위해 BFS를 사용합니다.방문 처리방문한 칸을 추적하여 중복 방문을 방지합니다.거리 기록현재까지 이동한 거리를 maps 배열에 기록하여, 각 칸에 도달하는 데 필요한 최소 이동 횟수를 저장합니다.종료 조건도착점에..

오늘의 문제인 침투를 풀어보았다. 기본적인 BFS & DFS로 풀 수 있었다. https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net dfs 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): per_lst[y][x] = 2 for dy, dx in d: Y, X = y+dy, x + dx if (0

BFS로 푸는 기본적인 문제 중에 하나인 토마토 문제를 풀어보았습니다. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 저의 풀이는 5가지로 나눴습니다. 1. 맵과 n,m을 입력받는다. 2. 토마토가 있는 1의 지점을 받고 queue에 저장한다. 3. bfs에 넣어서 queue에서 pop 해주어 동서남북으로 탐색 후 0을 발견하면 지금 자리에 +1을 하여 맵에 업데이트 후 queue에 해당 좌표를 넣어준다. 4. queue가 비..