🔗문제 보러가기 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 🧑‍💻풀이 과정 DFS + 백트래킹으로 풀 수 있는 문제입니다. 처음에는 같은 문자 방문 여부를 위해 set을 이용했는데, 시간 초과가 나더라구요. 그래서 시간을 줄이기 위해 다른 방법을 생각했는데, 알파벳은 26개가 있고 각각 한 번씩만 방문할 수 있으니, vector Alphabet(26, false) 배열을 통해 방문 여부를 관리하니 통과가 되었습니다. \(\mathrm{O(1)} \) 과 \( \mathrm{O(log \ N)..

🔗문제 보러가기 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🧑‍💻풀이 과정 연구소의 크기가 최대 \(8 \times 8\) 이기 때문에 벽을 3개 설치하는 모든 경우의 수에 대해 탐색하여 풀었습니다. 백트래킹과 BFS 탐색을 잘 구현하는 것이 목표인 문제인 것 같네요. 2차원 배열에 연구소 정보를 입력 받고, 바이러스의 위치 정보도 별도의 배열에 저장한다. 조합(Combination) 방식을 이용해 열 방향 순서로 벽 3개를 설치한다. 빈 공간일 때에만 벽을 설치한다. 벽을 3개 설치 다 했다면, 3번 과정을 진행 후..

🔗문제 보러가기 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 👨‍💻풀이 과정 BFS + DFS + 최소 신장 트리(MST) 알고리즘을 구현해야 풀 수 있는, 대단히 체력적으로 힘든 문제였습니다. 그래도 문제에서 주어진 조건들이 까다롭진 않아, 구현만 제대로 한다면 통과는 쉽게 되네요. 제가 푼 과정은 다음과 같습니다. 주어진 입력을 2차원 배열에 저장하되, 땅(1)은 1이 아니라 엄청 큰 다른 숫자(1억)로 대신 채워줍니다. BFS 알고리즘을 통해, 각 섬의 번호를 해당 섬의 영역에 채..

🔗문제 보러가기 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🧑‍💻 풀이 과정 최단 경로 알고리즘을 연습 중에 있어, 저는 다익스트라 알고리즘으로 풀었습니다. (비용에 음수가 없기 때문) 시작 위치는 N, 도착 위치는 K로 주어집니다. N에서 i번째 노드로 가는 데에 드는 최소 시간을 저장하는 배열, times를 선언합니다. 범위가 0 ~ 100,000이니, 이 범위를 포함할 수 있는 만큼의 크기로 선언 후, 무한대 값으로 초기화합니다. times[N] = 0 으로 초기..

🔗문제 보러가기 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 🧑‍💻풀이 과정 BFS로 쉽게 풀 수 있는 문제인데, 저는 사다리나 뱀을 타고 간 보드칸을 방문 처리해주질 않아, 엉뚱한 답이 나왔습니다. 이걸 빨리 알아채지 못해서 시간을 좀 허비했네요. 아무튼, 제가 푼 풀이 과정은 다음과 같습니다. 뱀이나 사다리 정보를 가지고 있는 vector teleports(100 + 1)을 준비한다. teleports[i] = 0 👉🏻 뱀이나 사다리가 없음을 의미 telep..

🔗문제 보러가기 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🧑‍💻풀이 과정 string을 스택(stack)처럼 사용하여 풀었습니다. 정답을 저장할 string 변수(answer)를 따로 준비한 후, 주어진 문자열을 차례대로 순회하였습니다. 그리고 다음과 같은 과정을 진행해 주었습니다. 현재 읽은 문자열을 answer 변수에 넣습니다. 현재 읽은 문자열이 폭발 문자열의 마지막 문자와 같다면, 다음 과정을 거칩니다. answer와 폭발 문자열을 뒤에서부터 차례대로 읽으며 비교합니다. 두 문자열..