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를 써준다. 다만 이 문제가 껄끄러운 이유는 벽을 어떻게 세워야 최대안전영역이 나오는가이다. 따라서 우리는 벽을 세울 수 있는 모든 경우의 수를 구해서 ..