https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질 문제 시리즈의 4편이다. 다른점이 있다면 거쳐온 경로를 출력해야한다는것이다. move 리스트를 만들어서 새로운 점으로 도달하기전에 거쳐온 점을 저장해서 for문으로 출력해준다. 대신 값은 시작점부터 출력해야하기에 reveres를 해주었다. # 13913 숨바꼭질 from collections import deque def bfs(): queue = ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 최단경로를 찾기 위해서는 2*X의 위치로 이동하는 경우는 우선 순위로 처리해줄 수 있게해야한다. appendleft( ) 메서드로 덱의 앞쪽으로 둬서 우선처리해준다. 그 이후는 목표값을 구할 때 까지 구해준다. # 13549번 숨바꼭질 3 # 이동방향 [x+1, x-1, 2*x] 대신 시간소모는 [+1, +1, 0]이다. # 가장 빠른시간. from coll..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 # 7562번 나이트의 이동 # 배열의 크기는 가로, 세로가 I. 시작점, 목표점이 주어짐, 이동방향은 나이트의 이동 8개 # bfs는 최적의 수를 주기에 visited 안에서 이동할때마다 1씩 추가해준다. import sys from collections import deque input = sys.stdin.readline dx = [2, 2, -2, -2, -1, 1, -1, 1] dy ..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 # 2468번 안전영역 # 크기가 N인 정사각형, 시작지점 없음 직접 찾아야함 최소 높이와 최대 높이 구하기 # 배열은 graph, visited로 구분 import sys from collections import deque input = sys.stdin.readline def bfs(height, k, j): queue = deque() queue.append((k,j)) while queue..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 좌표문제는 주로 dfs로 문제를 푸는 편이다 이동할 수 있는 경우의 수를 따로 리스트에 담아둔 뒤 BFS로 모든경우의 수를 계산해서 graph에 저장해준다. # 1697번 숨바꼭질 # 시작값과 목표값도 주어짐 배열 한계는 0 - 100000 까지 # 이동방향은 3가지 [+1, -1, 이전값*2], 최적의 거리를 찾기에 bfs사용 import sys from coll..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS로 모든경우의 수를 visit에 저장해준 뒤 target값을 출력 # 5014번 스타트링크 from collections import deque floor, start, target, u, d = map(int, input().split()) visit = [0] * (floor+1) visit[0] = 1 dx = [u, -d] def bfs(): queue = deque() queue.appen..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 시작값과 목표값이 각 테스트케이스마다 주어진다. 시작값의 각 자리의 숫자를 바꿔가면서 소수를 유지하면서 목표값으로 바꿀 수 있는가? 1, 에라토스테네스의 체 알고리즘으로 1000 ~ 9999까지의 숫자들 중 소수만 뽑아서 리스트를 만들어준다.2, BFS를 실행해서 숫자의 각 자리를 1~9까지의 숫자로 바꿔가면서 목표값까지 이동할 수 있나 없나 확인한다.대신 첫방문이며 소수여야하고 1000이상인 숫자여..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 N: 지도의 세로 크기, M: 지도의 가로 크기, 지도좌표 값(바이러스(2), 벽(1)) 실버문제들 중에서도 흔히 볼 수 있는 바이러스나, 토마토 문제처럼 특정한 값을 가진 칸에 인접한 칸들에게 영향을 주는 문제이다. 나는 이런 문제가 나올 때마다 BFS를 써준다. 다만 이 문제가 껄끄러운 이유는 벽을 어떻게 세워야 최대안전영역이 나오는가이다. 따라서 우리는 벽을 세울 수 있는 모든 경우의 수를 구해서 ..