BFS8 [BOJ] 백준 11060번 - 점프 점프(with Java) 알고리즘 미로에서의 현재 위치와 이동 횟수를 구하기 위해서 Node 클래스를 정의한다. 0번 이동한 상태에서 0번 위치에서 시작할 때 만들어지는 객체로 BFS를 시작한다. 현재 위치 idx에서 한번에 최대 arr[idx]만큼 이동할 수 있으므로 각각의 경우에 대해서 조건에 부합하는지 확인하고 탐색한다. 조건에 부합하면 방문처리해주고 다음 방문할 위치 idx와 time+1을 객체로 만들어서 큐에 넣어준다. 큐에서 꺼낸 객체의 번호가 끝 번호라면, 해당 객체의 time을 출력하고 종료한다. 소스코드 문제링크 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는.. 2022. 6. 30. [BOJ] 백준 18405번 - 경쟁적 전염(with Java) 알고리즘 바이러스의 위치와 몇 초에 바이러스가 퍼졌는지 계산하기 위해서 Virus 클래스를 생성한다. 배열의 원소를 입력받을 때 값이 1이상인 경우에 대해서 grid[i][j]에 해당하는 인접 리스트에 좌표값을 갖고 있는 Virus 객체를 각각 삽입한다. 1부터 K까지의 바이러스 번호를 보유한 인접리스트로부터 좌표값을 갖고 있는 Virus 객체를 큐에 각각 추가한다. BFS를 수행하면서 다음 위치로 이동할 수 있을 때마다 좌표값과 현재 바이러스가 퍼지기까지 걸린 시간으로 Virus 객체를 구성한다. 위의 과정을 바이러스가 퍼지기까지 걸린 시간이 S인 Virus 객체를 큐에서 꺼낼 때까지 수행한다. 소스코드 문제링크 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다... 2022. 6. 28. [BOJ] 백준 1697번 - 숨바꼭질(with Java) 알고리즘 N에서 BFS를 시작한다. 가장 빨리 찾은 시간을 게산하기 위해서 idx와 time을 원소로 가지는 Node 클래스를 생성한다. 총 3가지의 행동 X-1, X+1, X*2을 할 수 있으므로 각각의 경우에 대해서 이동할 수 있는지 확인한 후에 방문 처리 및 time을 1 증가시켜서 큐에 넣어준다. 큐에서 꺼낸 node.idx의 값이 K와 일치하면 answer에 값을 저장하고 반복문을 탈출한다. 소스코드 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2022. 6. 28. [BOJ] 백준 2644번 - 촌수계산(with Java) 알고리즘 1. BFS를 할 때마다 특정 번호의 촌수를 계산하기 위해서 Node 클래스를 선언한다. 2. 먼저 주어지는 사람의 번호를 src, 나중에 주어지는 번호를 dsc라고 정의한다. 3. 주어진 값들을 입력받을 때 아직 촌수를 알 수 없기 때문에 각 번호에 대한 촌수를 0으로 초기화한다. 4. BFS로 dst를 찾을 때까지 각각의 Node를 탐색하면서 cur.degree를 1씩 더하는 방식으로 번호들의 촌수를 초기화한다. 5. 큐에서 꺼낸 Node의 번호가 dst와 같으면 cur.degree를 반환한다. 6. 만약에 모든 Node를 탐색할 때까지 dst를 찾지 못하면 -1을 반환한다. 소스코드 문제링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각.. 2022. 6. 26. [BOJ] 백준 1260번 - DFS와 BFS(with Java) 알고리즘 1. DFS와 BFS로 탐색한 결과를 저장하기 위해서 'dfsAnswer', 'bfsAnswer'를 각각 리스트로 만든다. 2. 방문할 정점이 여러 개인 경우, 값이 작은 정점을 먼저 방문하므로 각각의 인접리스트를 오름차순으로 정럴현다. 3. DFS, BFS를 통해서 도출된 결과들을 각각 'dfsAnswer', 'bfsAnswer'에 넣어주고 탐색이 모두 끝나면 한번에 출력한다. 소스코드 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2022. 6. 26. [BOJ] 백준 9205번 - 맥주 마시면서 걸어가기(with Java) 알고리즘 아이디어를 떠올릴 수 있다면, Floyd-Warshall 알고리즘을 이용해서 간단하게 BFS로 풀 수 있는 문제이다. 설계를 잘했다면 문제를 푸는 방법은 매우 간단하다. 우선, 각각의 위치를 정의해줘야만 하는데 좌표가 음수가 될 수도 있으므로 배열을 이용한 풀이는 어렵다. 따라서 현재 위치 x, y 좌표와 해당 위치의 방문 여부 정보 및 시작점과의 거리 정보를 담고 있는 클래스를 만들어준다. 또한, 모든 편의점과 목적지는 시작점과의 거리 정보를 무한대로 설정해주고 각각의 객체들을 리스트에 넣어준다. 이제부터 각각의 정점들에 대해서 BFS를 수행하면 되지만, 여기서 고려해줘야할 사항이 하나 있다. 문제에서 주어진 '맥주 한 박스에는 맥주가 20개 들어있다', '50미터를 가려면 그 직전에 맥주 한.. 2021. 12. 15. [BOJ] 백준 7562번 - 나이트의 이동(with Java) 알고리즘 [BOJ] 2178번 - 미로 탐색 문제와 마찬가지로 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위한 별도의 클래스(Vertex)를 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야 한다. 나이트는 최대 8방향으로 이동할 수 있기 때문에 미로 탐색 문제에서 설명했던 것과 마찬가지로 탐색에 위험부담이 있는 DFS를 사용하지 않고 탐색 효율이 좋은 BFS를 사용한다. 또한, 미로 탐색 문제에서와 동일하게 나이트가 출발점에서 도착점까지 갈 수 있는 최단거리를 찾기 위해서 각각의 정점에 대한 부모 배열을 만들었고, 탐색이 끝난 후에 도착점으로부터 부모 배열을 타고 올라가서 시작 정점을 찾는 방식으로 최단거리를 구하였다. 미로 탐색 문제와의 차이점은 단지 방향이 4개에서 8개로 늘어.. 2021. 7. 11. [BOJ] 백준 2178번 - 미로 탐색(with Java) 알고리즘 인접리스트를 사용해서 문제를 풀었던 [BOJ] 1260번 - DFS와 BFS와는 달리 2차원의 미로에서 최단거리를 찾기 위한 그래프 탐색은 조금 복잡하다. 우선 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위해서 'Vertex' 클래스 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야한다. 이 문제는 위험부담이 있는 DFS와는 달리 효율이 좋은 BFS를 사용하여 풀기로 결정하였다. DFS는 최단거리를 한번에 찾는 경우에 최고의 효율을 보이지만, 그렇지 못하는 경우에는 백트래킹을 통해서 다른 경로를 재탐색해야하는 문제가 발생한다. 반면에 BFS는 그물망을 펼치는 것처럼 모든 경로를 넓지만 천천히 탐색하기 때문에 경로를 재탐색하는 문제가 발생하지 않는다. 따라서 이 문제의 경우에.. 2021. 7. 11. 이전 1 다음
