알고리즘 풀이/BFS(너비 우선 탐색)
-
BOJ 9184 [신나는 함수 실행]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:03
BOJ 신나는 함수 실행 : www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 신나지 않은 함수 실행이다. 메모이제이션을 사용해 풀었다. 배열 인덱스에 50을 더한 이유는 마이너스도 있으니깐,, 밑에 코드는 +50때문에 눈이 좀 피곤할 수도 있다. 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..
-
BOJ 17836 [공주님을 구해라!]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:00
BOJ 공주님을 구해라! : www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 간단한 BFS 문제이다. 키포인트는 방문배열(visit)를 3차원으로 설정했다. visited[3][3][0] => 그람 없이 (3, 3)을 방문한 경우 visited[3][3][1] => 그람을 가지고 (3, 3)을 방문한 경우 그람을 획득하면, 해당 node가 그람을 가지도록 체크해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
BOJ 17141 [연구소 2]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 4. 23:08
BOJ 연구소 2 : www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 옛날에 연구소는 풀어봤는데, 2탄도 있는줄 몰랐다. 나의 풀이 방법은 다음과 같다. 바이러스를 놓을 수 있는 구역을 먼저 체크해 vector에 담아놓는다. 브루트 포스를 이용해 바이러스를 놓는 모든 경우의 수를 체크한다. BFS로 바이러스를 확산시켜본다. 제출하니 420ms나 걸린다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..
-
BOJ 11559 [Puyo Puyo]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 15:52
BOJ Puyo Puyo : https://www.acmicpc.net/problem/11559 어릴때 했던 뿌요뿌요가 생각나는 문제입니다. 시뮬레이션 부분이 SWEA 벽돌 깨기와 유사했습니다. 1. BFS를 돌며 인접한 같은 색 뿌요를 찾는다. 2. BFS를 빠져나오면 탐색 완료된, 인접한 같은 색 뿌요의 개수를 저장한다. 3. 4 이상으로 저장된 뿌요를 삭제한다. 4. 뿌요를 하강시킨다. 5. 삭제할 뿌요가 없을 때 까지 1~4 반복 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980..
-
BOJ 2146 [다리 만들기]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 06:28
BOJ 다리 만들기 : https://www.acmicpc.net/problem/2146 안녕하세요. 이번 문제는 백준 온라인 저지의 [다리 만들기] 입니다. 1. BFS로 현재 위치에서 갈 수 있는 곳을 확장시킨 뒤, BFS를 빠져나올 때 마다 해당 섬에 번호 부여. 2. 다시 처음부터 BFS를 돌며, 첫 시작지와 섬 번호가 다른 섬을 찾아 떠난다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485import java.util.*;class Node { public ..
-
BOJ 1726 [로봇]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 06:20
BOJ 로봇 : https://www.acmicpc.net/problem/1726 이번 문제는 백준 온라인 저지의 [로봇] 입니다. 재방문을 방지하기위해 Visited를 사용했습니다만, 3차원으로 방향에 대한 방문도 고려하도록 했습니다. 로봇이 할 수 있는 행동인 1~3칸 앞으로 가기, 방향 꺾기 등을 큐에 담으며 탐색을 진행합니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include using namespace std;int M..
-
BOJ 2234 [성곽]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 2. 03:31
BOJ 성곽 : https://www.acmicpc.net/problem/2234 안녕하세요. 이번 문제는 백준 온라인 저지의 [성곽] 입니다. 우선 1, 2번 요구사항의 경우는, 기본적인 BFS문제입니다. 다만, 입력이 평소의 문제와 조금 다릅니다. 우선, 이진법을 통해 각 위치의 동서남북을 1로 설정합니다. 여기서 MAP을 2배 늘려서 이동을 2칸씩 하고, 벽은 한칸 뒤에 놓았습니다. 다음 3번에서 사용한 방법입니다. 1. 먼저 BFS를 통해 구한 방의 size와 방 번호를 노드 배열형태로 저장. 2. for문을 돌면서, 인접 좌표의 방번호가 다르면, 해당 방의 size를 비교 모든 좌표를 돌면서, 상하좌우를 확인하고 방 번호가 다를 때, 방의 사이즈를 더한 값의 최대를 구하면, 벽을 뚫을 때의 최대..
-
BOJ 1600 [말이 되고픈 원숭이]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 9. 23. 04:21
BOJ 말이 되고픈 원숭이 : https://www.acmicpc.net/problem/1600 안녕하세요. 이번 문제는 백준 온라인 저지의 [말이 되고픈 원숭이] 입니다. BFS를 단순하게 사용하면 풀릴 것 같지만, 함정이 있었습니다. 말처럼 움직였을때의 위치와, 그냥 한번 움직였을 때의 위치가 같을 경우에, 좌표가 같아도 그 경로가 다를 수 있습니다. 쉽게말해서 말의 움직임을 아껴놨다가 사용해야할 경우가 생길 수 있습니다. 하지만 먼저 기회를 사용해 해당 좌표에 도달한 것을 체크한다면, 나중에 기회를 아꼈을 경우 해당 좌표가 Visited되있어 재방문을 할 수 없습니다. 그래서 Visited를 3차원으로 만들었습니다. 1234567891011121314151617181920212223242526272..