https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 풀이 문제 풀이는 BFS를 기본적으로 사용하고, 도시와의 거리 단위는 1이기 때문에 방문시 현재 도시 기준에서 1을 더해준다. import sys from collections import deque input = sys.stdin.readline n, m, k, x = map(int, input().split()) g..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 다른 BFS 문제들은 풀이 방식이 유사했으나 이번 문제는 구현 + BFS 문제이기에 처음 풀어보는 유형이었다. 그래서 30분정도 고민하다가 벽을 어떻게 세워야 할지 모르겠어서 특성 블로그의 글이 아닌 구글링을 통해 다른 사람들의 여러 풀이를 찾아봤다. 다른 사람의 풀이를 찾아보면서 벽을 세우는 방법은 완전 탐색으로 세워야 하며, 백트래킹이라는 기법으로 세워야 한다는 것도 알게 되었다. 백트래킹은 처..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 이번 문제는 7576번 문제를 3차원으로 생각하여 풀면 되는 문제이다. import sys from collections import deque input = sys.stdin.readline m, n, h = map(int, input().split()) graph = [[list(map(int, input().split())) for _ in range(n)]..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 처음에는 그리디 문제인줄 알고 그리디 방식으로 풀려고 하였다. 떠오른 풀이 방법은 Top down 방식으로 예제 입력값이 5와 17일 때 17부터 숫자를 줄여나가며 정답을 찾는 방식이다. 알고리즘 작동 방식은 다음과 같다. 1. -1 or +1 해보고 n과 일치하는지 확인. 2. n과 일치하지 않는다면 짝수인지 홀수인지 확인 (짝수라면 2로 나누고, 홀수면 -..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 이번 문제 역시 기본적인 BFS 틀을 활용하여 푸는 문제였다. 처음에 여러가지 시도를 하였다. 토마토가 총 몇개 익을지는 이전 문제들에서 푼 방식을 적용하여 풀면 되었는데, 토마토가 익는데는 하루가 걸리는데 이 하루를 어떻게 묶을지가 어려웠다. 고민 끝에 찾아낸 규칙은 큐가 들어가고 나서 상하좌우를 탐색하는 동안 처음 큐에서 나온 x와 y의 값은 동일하다는 점이다. 이 ..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 이 문제는 2667 - 단지번호붙이기와 풀이 방식이 거의 유사했다. 기본적으로 BFS/DFS 문제들은 풀이 방식이 비슷한데 약간의 변화와 응용만 해주면 되는거 같다. 가장 먼저 떠오른 생각은 각 위치를 돌아다니며 1로 표시된 곳이 어딘지 확인해야 하기 때문에 기본적인 BFS 틀을 함수를 작성한 후에 dx와 dy라는 별도의 방향 리스트를 만들어 구현했다. import sys from collectio..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 이 문제는 BFS와 DFS를 응용하여 풀이하는 문제이다. 두 가지 방법 중 BFS를 선택해 구현을 진행하였고, 첫번째 단지를 바로 찾을 수 있었다. from collections import deque import sys input = sys.stdin.readline n = int(input().rstrip()) graph = [] for _ in range(n): graph.appen..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제 역시 아직 bfs에 익숙하지 않기 때문에 다른 사람의 풀이를 보며 유형을 익힌다는 느낌으로 찾아보았다. from collections import deque n, m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input()))) def bfs(x, y): dx = [-1, 1, 0, 0] dy = [0, 0, ..