본문 바로가기
반응형

BFS6

BOJ 14502 - 연구소 / C++ 문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 세울 수 있는 경우의 수는 DFS로 완전탐색하고 그렇게 생성된 배열을 다시 BFS로 순회하며 바이러스를 퍼뜨리고 안전 영역을 세야한다. 우선, 입력 받은 배열을 돌며 0(빈 칸)을 발견하면 해당 지역부터 DFS를 시작한다. 해당 지역에 벽(1)을 세우고 DFS 카운트를 늘려준 뒤 다시 배열을 돌며 다음 0(빈 칸)을 찾는다. 이렇게 DFS의 카운트가 3이 되면 벽을 모두 세웠으므.. 2022. 5. 4.
프로그래머스 - 경주로 건설 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 기본 베이스는 BFS이고 memoization 기법을 추가로 적용하.. 2022. 4. 24.
BOJ 16928 - 뱀과 사다리 게임 / C++ 문제 링크 : https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 입력 받을 때, 뱀과 사다리를 굳이 나누어 입력받을 필요 없이 하나의 지름길로 취급하여 n+m만큼 입력받는다. 지름길 변수 shortcut[a] = b의 의미는 a로 들어가면 b로 나오게 된다는 의미이다. 다음으로, BFS를 통해 시작점 1 카운트 0부터 시작하여 1~6의 주사위에 따른 탐색을 진행한다. 도중에 지름길을 만나면 지름.. 2022. 4. 18.
BOJ 4486 - 녹색 옷 입은 애가 젤다지? / C++ 문제 링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 다익스트라와 BFS가 섞인 문제이다. 현재 노드에서 이동할 수 있는 경우는 우, 하, 상, 좌 순서로 한칸 씩이다. 먼저, 다익스트라 알고리즘처럼 dist 배열을 모두 INF로 초기화 시킨 뒤 (0, 0)에서 출발한다. 정점을 탐색하며 dist 배열을 업데이트할 수 있다면 업데이트한 뒤 해당 정점으로 이동한다. dist 배열이 모두 업데이트 되었으면 (n-1,.. 2022. 3. 20.
반응형

티스토리툴바