그래프 탐색 (9) 썸네일형 리스트형 [백준 9376][C++] 탈옥 문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 과정 [참고 링크 1] [참고 링크 2] [0-1 BFS 알고리즘 링크] 필자는 링크 1의 코드를 기반으로 풀이를 작성했다. 해당 문제는 0-1 BFS 알고리즘을 통해 다익스트라 알고리즘보다 효율적으로 구현할 수 있다. 주변의 위치에 존재하는 BFS탐색 시, 문이거나 문이 아닌 경우로 나뉘기 때문이다. 이 문제의 핵심은 아래 3가지 경우를 모두 고려해야 한다는 점이다. 1) 1번 죄수가 탈출하며 문.. [백준 2933][C++] 미네랄 문제 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 과정 1. 문제 조건에 맞게 입력을 받는다. 2. 순서대로 발사하여 미네랄을 부순다. 3. 부순 미네랄을 기준으로 주변을 탐색하여 미네랄 군집(cluster)을 파악하고, 중력에 의한 이동을 수행한다. 4. 최종 형태를 출력한다. 세부 풀이 (1) 초기 형태와 이후 던질 막대의 높이에 대한 정보도 한 번에 입력받아 order 배열에 넣어 저장한 뒤 사용했다. (2) shoot 함수 order 배열에 .. [백준 3197][C++] 백조의 호수 문제 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 풀이 과정 해당 문제를 정말 많이 고민하면서 풀었지만 계속 메모리 초과가 발생했다. 메모리 초과에 의해서 문제를 풀지 못했던 적은 처음이라 이런저런 경우를 많이 테스트해보며 과정을 적으려 한다. 1) int -> char 변경 (실패) 처음엔 전체 호수의 상태를 저장하기 위해 int map [1501][1501]를 이용했었는데, 여기서 메모리가 초과되었나 하고 고.. [백준 21609][C++] 상어 중학교 문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 1. 회전 함수 구현 2. 중력 함수 구현 3. 탐색을 통해 가장 큰 블록을 찾는 함수 구현 블록 수 같은 경우 무지개 블록 확인 무지개 블록 수 같으면 기준 블록 확인 4. 블록 찾아서 제거, 중력, 회전, 중력 순으로 수행되는 하나의 사이클 생성 5. 만약 찾은 최대 블록의 수가 1개 이하라면 그룹이 없는 것이므로 종료하며 현재까지 점수의 합 출력 세부 풀이 (1) rota.. [백준 20058][C++] 마법사 상어와 파이어스톰 문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net [참고 풀이 링크 : YJYOON`s Code Story] 해당 문제의 풀이 시간이 개인적으로 정했던 기준 시간을 초과하여 풀지 못했으므로 다른 분의 코드를 참고하여 공부하였습니다. 회전하는 함수의 논리와 dfs를 통한 간결한 구현을 배울 수 있는 좋은 풀이라고 생각하였습니다. 해당 코드에 대한 저의 생각을 아래 형식에 맞게 서술하도록 하겠습니다. 풀이 과정 1. 격자 사.. [백준 19238][C++] 스타트 택시 문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 과정 1. 입력받은 모든 정보를 저장 2. 입력받은 좌표를 기준으로 입력받은 위치에서의 각 칸의 최단거리를 구하는 함수를 구현 (BFS 알고리즘 이용) 3. 문제 조건에 맞게 가장 짧은 승객을 태우고, 운행하는 함수를 작성한다. 4. 3번 함수를 수행하고 택시를 이용한 승객이 입력받은 승객의 수보다 적다면 -1을 출력하고, 모두 이용했다면 현재 연.. [백준 17142][C++] 연구소 3 문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제에서 주어진 제한 시간이 짧음에 주의하여 구현해야 한다. 풀이 과정 1. 주어진 입력에 주어진 바이러스의 위치 중 활성화할 바이러스를 선택할 수 있는 경우 탐색 알고리즘 구현(DFS, 조합 이용) 2. 선택된 바이러스의 위치에서 BFS를 통한 전이 함수 구현 3. 1에서 구현한 알고리즘을 통해 2를 반복하며 최소 전파시간 업데이트 4. 모든 탐색을 마친 후 최소 전파시간 출력 첫 제출에서 시간 초.. [백준 13460][C++] 구슬 탈출 2 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [참고 링크] 이 문제는 스스로 풀지 못하였고, 참고한 링크의 코드를 이해한 내용을 바탕으로 설명하였다. 풀이 과정 1. 문제 조건에 맞도록 기울여 이동하는 함수를 작성한다. 2. 4방향으로 각각 탐색을 진행하며, 이동을 통해 빨간 공이 구멍에 들어간 경우 현재까지 기울인 횟수를 출력하고 탐색을 종료한다. 이때 파란 공이 구멍에 들어간 경우는.. 이전 1 2 다음
