본문 바로가기

BFS

 (29)
[백준 / BOJ] 18500 미네랄 2 (Java) / 2933 미네랄 1 포함 미네랄 2 기준으로 설명을 하겠다. (미네랄 1(2933번)과 2는 동일한 문제인데, 미네랄1이 테스트케이스가 좀더 빡샌거로 알고있다.) 실제로 동일 코드를 제출하면 모두 맞았습니다가 나온다. 문제 출처 : https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 창영이와 상근이가 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 던져 싸우고있는데, 막대기가 날아가다 미네랄을 만나면, 해당 미네랄은 파괴되고 막대기도 이동을 멈춘다. 이때, 해당 미네랄이..
[백준 / BOJ] 1445 일요일 아침의 데이트 (Java) 문제 출처 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다. 숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다. 이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나..
[백준 / BOJ] 1938 통나무 옮기기 문제 출처 : https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4
[백준 / BOJ] 1039 교환 문제 출처 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 0으로 시작하지않는 정수 N이 주어진다. 정수 N의 자릿수 M에 대해 다음과 같은 연산을 K번 수행했을때, 나올수있는 최댓값을 계산하는 프로그램이다. 1 13 -> 31 과 같은 루트로 이동해 최댓값을 찾을수도 있기때문이다. 따라서, 체크배열을 map check; 와 같이 선언한다. (cnt번 이동해서 vector 형태가 되었을때, 이동횟수) 위 정보들을 갖고 구현하면된다. -1 출력은 1. N이 한자릿수 인경우 2. N이 두자릿수면서 일의자리가 0인경..
[백준 / BOJ] 9376 탈옥 문제 출처 : https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 상근이는 감옥에서 죄수 두명을 탈옥시킬려고한다. N*M크기의 감옥이있고, 감옥은 # : 문 . : 빈 공간 $ : 죄수 로 구성되어있으며, 죄수는 항상 2명이다 (문이 있는곳은 지나가기위해 문을 열어야한다.) 모든 죄수를 탈출시키기 위해서 열어야 하는 문의 최솟값을 출력하는 문제였다. 풀이 다익스트라로 풀은 문제다. 처음 문제를보고 그냥 BFS를 돌리면 될것같다고 생각했는데, 한 죄수가 밖으로 ..
[백준 / BOJ] 3197 백조의 호수 문제 출처 : www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 호수에 백조 두마리가 살고있다. 호수의 어떤칸은 얼음으로 덮여있으며, 매일 물과 접촉해있는부분은 녹는다. 백조는 얼음이 없는 위치로 움직일수있을때, 두 마리의 백조가 만나기위해 걸리는 최소 시간을 구하는 문제다. 풀이 BFS와 다익스트라로 푼 문제다. 백조는 움직일때 시간이 걸리지않는것에 유의해야했다. 구현은 백조가 어떤칸에 가기위해선 해당칸까지 가는 경로가 전부 얼음..
[백준 / BOJ] 2638 치즈 문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net N*M크기의 모눈종이에 치즈가 있다. 모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다. 가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다. 풀이 BFS,DFS를 이용한 시뮬레이션 문제다. N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다..
[백준 / BOJ] 14502 연구소 문제 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net N*M그리드가 주어지고, 그리드의 상태가 주어진다. 0 : 빈칸 1 : 벽 2 : 바이러스 바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다. 풀이 N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다. 시간복잡도는 1. N*M그리드 에서 3개의 빈칸을 선택하는 경..

티스토리툴바