BFS

https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 📝문제 📝풀이 우선순위큐를 이용한 bfs 하는 문제이다. 우선시 되어야 하는 기준은 1. 쓰레기를 지나지 않는 것 2. 쓰레기 근처도 지나지 않는 것 그런데 2 번 조건을 처리하기 위해 처음 입력때 받은 g 를 list 안에 넣고 list를 순회하면서 map의 값이 '.' => 'm' 으로 바꾸고 bfs를 수행할 Queue 의 Comparator를 정해 주었다. 출발지..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 📝문제 📝풀이 구슬을 이동시키다가 빨간색 구슬만 구멍에 빠지는 최소 move 카운트를 return 하는 문제이다 우선 최소 횟수는 좌표 BFS 특성상 먼저 끝내는 것이 최소 횟수 이므로 종결조건을 만족하기만 하면 return 1. 총 4방향 {아래, 위, 오른, 왼} 으로 움직이는데 벽인 '#' 기호를 만날 때 까지 움직인다 2. 파란색 구슬의 좌..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 📝 문제 📝 풀이 S 초 뒤에 해당 위치 (X,Y) 의 바이러스 상태를 return 하는 문제이다. 바이러스가 퍼지는 조건은 번호 순 대로 차례대로 퍼진다 따라서 순위를 보장해 주는 우선순위큐에 주어진 map 의 좌표를 다음과 같은 순서로 넣는다 1. 시간순 2. 번호순 BFS를 수행하면서 탐색 할 위치에 바이러스가 없다면 map 의 값을 갱신 만약 종결조건인 S 시..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [문제] [풀이] 주어진 조건을 만족할 때 까지 반복하여 BFS를 돌려야 하는 문제이다. 주어진 조건의 종결조건 => 더 이상 인구 이동을 하지 않을 때 따라서 BFS를 돌리며 연합 가능한 국가들의 인구를 계속해서 구한 평균치로 새로 설정하고 더 이상 이동할 필요가 없을 경우엔 break를 걸어 빠져 나오면 된다 import java.util.*; import java.io.*; i..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [문제] [풀이] 기본적으로 좌표 Map 에서 BFS를 시행하면 최단경로로 가기때문에 다익스트라랑 유사한 알고리즘으로 동작한다. 일반적인 BFS로 풀이하되 벽을 부수는 경우가 추가로 생겼기 때문에 이에 대한 check를 나타내야함 visit 방문확인 배열을 3차원으로 하여 크기는 k+1로 둔다. (벽을 안 부쉬는 경우도 있기 때문) 벽을 부술때마다 +1 씩하여 ..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 풀이 탐색 문제이다. 우선 섬의 갯수를 세고 각 섬마다 다른 숫자로 라벨링을 해준다. (초기1-> 2,3,4, .... ) 섬 아무곳에서 출발하여 바다면 움직인거리+1 다른 섬을만나면 섬섬 거리 최소거리 갱신 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 아 .. 비트마스킹이란걸 몰라서 한참을 헤매었다.. 결론적으로는 열쇠의 유무를 2^6 = 64 , 즉 visit배열을 3차원으로 열쇠유무까지 추가하면 => visit[높이][너비][열쇠] visit[h][w][64] 이렇게 두고 풀어야 한다는 것이다. 열쇠면 | 연산으로 추가 , 문 이면 & 연산으로 확인하는 식으로해서 탐색을 하면 된다. 1 2 3 4 5..

https://www.acmicpc.net/problem/16197 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 동전 위치를 나타내는 Point 객체와 두 동전을 담고 움직이는 횟수를 나타내는 Move 객체를 생성 2. 우선순위큐를 이용하여 횟수가 적은 순서대로 처리 3. isRange(x,y) 로 범위를 벗어나는 조건을 이용해서 둘 중 하나만 떨어지는 경우를 체크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..