[BOJ] 13913. 숨바꼭질 4
문제 숨바꼭질 4 (https://www.acmicpc.net/problem/13913) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이전 12851. 숨바꼭질 3 문제에서 방법에 약간 변형을 준 것이다. 이제는 경로를 출력해야하는데, DFS야 쉽게 탐색 경로를 출력할 수 있다지만, BFS 에서는 어떻게 해야할까? 현재 위치 cur 에 오기 직전 위치를 담는 리스트(path_list)를 만들자. 예를 들어, 현재 위치가 3이고, 다음으로 이동할 위치가 2, 4, 6이면, path_list[2], path_list[4], path_list[6] = 3 이 된다. 물론 여기에도, 최소 시간으로 왔는지 체크해야 한다. 그리고 최종 ..
[BOJ] 13549. 숨바꼭질 3
문제 숨바꼭질 3 (https://www.acmicpc.net/problem/13549) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이전 12851. 숨바꼭질 2 문제에서 방법에 약간 변형을 준 것이다. 이전 문제에서는, 현재 위치 cur에서 다음 위치 cur-1, cur+1, cur*2 를 한번에 처리했다면, 이번엔 경우를 나눠야한다. 먼저, visited[cur] 는 cur 위치에 올 때 걸리는 최소 시간을 담는다. cur-1, cur+1 로 이동하는 경우, 현재 위치까지 걸린 시간 + 1 을 해준다. 즉, visited[cur-1], visited[cur+1] = visited[cur] + 1 이다. 이 때, 당연히 이..
[BOJ] 7569. 토마토
문제 토마토 (https://www.acmicpc.net/problem/7569) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 이전 7576. 토마토 문제에서 위아래 방향만 추가한 것이다. 코드 import sys from collections import deque dzs = [0, 0, 0, 0, 1, -1] dxs = [-1, 0, 1, 0, 0, 0] dys = [0, -1, 0, 1, 0, 0] m, n, h = map(int, sys.stdin.readline().split()) board, q, visited = [], deque(), set() for _ in range(..
[BOJ ]7576. 토마토
문제 토마토 (https://www.acmicpc.net/problem/7576) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 코드 import sys from collections import deque dxs = [-1, 0, 1, 0] dys = [0, -1, 0, 1] m, n = map(int, sys.stdin.readline().split()) board, q, visited = [], deque(), set() for _ in range(n): board.append(list(map(int, input().split()))) for i in range(n): for j i..
[BOJ] 16397. 탈출
문제 숨바꼭질 (https://www.acmicpc.net/problem/1697) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 전체적으로 1697.숨바꼭질 과 동일한 문제다. 다만, 여기서 신경써야할 부분은, 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 이 부분이다. 언어에 따라 다르게 처리할 수 있겠지만, 파이썬은 그래도 str() 이나 int() , .join() 을 통해 쉽게 처리할 수 있다. 아래 코드를 보면 된다. 코드 import sys n, t, g = list(map(int, sys.stdin.readline().split())) def bfs(n, t, g): ..