BOJ 11567번 <이모티콘>
난이도 :골드 4
알고리즘 분류 :그래프 탐색
문제의 접근 방식
현재의 단계에서 다음 단계로 나아가는 선택지의 수가 명확하고
최단 시간을 묻는 문제기 때문에 BFS 알고리즘을 사용하여 접근하였다.
BFS 알고리즘은 큐를 사용해 구현하였다.
매번 달라지는 클립보드의 이모티콘 수와 화면에 출력된 이모티콘을 어떻게 갱신하고 저장할까를 고민하다가 queue<pair<int, int>> 형태의 큐를 사용해 <화면 출력, 클립보드> 쌍으로 데이터를 저장하였다.
문제는 풀이 방법은 알겠는데 런타임 에러와 메모리 초과 문제가 발생하였다는 점이다.
메모리 초과 의 경우는 일전에 풀었던 실버 1 난이도의 BFS 알고리즘 문제를 풀다가도 발생하였는데, 같은 값을 중복해서 큐에 넣는 방식이 메모리 초과를 발생시키는 경우가 많은 것 같다. 따라서 visit[][] 배열을 사용해서 방문 체크를 해주면 중복 값의 push 를 방지할 수 있다.
시간낭비를 가장 많이 한 이유는 런타임 에러 때문이다. 배열 인덱스 참조 오류때문에 발생한다는 점은 알고있지만.. 어떤 부분인지 찾아내는데 생각보다 많은 시간을 들였다. 아직 경험이 많이 부족하다고 느꼈다.
이런 식의 조건문에서 런타임 에러가 반복적으로 발생하였는데도 나는 어떤 점이 문제인지 파악하지 못하고있었다. 그림 상으로는 이중 if 문으로 보이지만 고쳐지기 전에는 두개의 조건문이 하나의 조건문에 합쳐져있었다.
바깥의 조건문은 인덱스의 범위를 체크하고, 안쪽의 조건문은 인덱스 방문체크를 하는데 두개를 합치면 안쪽에 해당하는 조건문에서 런타임 에러가 발생할 수 밖에 없는 것이다.
pair 큐를 사용하여 데이터를 저장, 갱신 하는 방법을 떠올리는 점을 제외하면 문제 풀이 로직보다는 메모리 초과, 런타임 에러가 애를 먹이는 문제였다. 풀이 코드는 다음과 같다.
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
queue<pair<int, int>> q;
int N;
int cnt = 1;
int visit[2000][2000];
// copy = 1 의 경우 put 가능
void bfs(int start) {
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int current = q.front().first; // 현재 총 출력 이모티콘 수
int buff = q.front().second; // 클립보드 이모티콘 수
if (current == N) {
return;
}
q.pop();
if ((current + buff) < 2000) {
if (!visit[current + buff][buff]) {
q.push({ current + buff, buff }); // 현재 내용 + 기존 클립보드
visit[current + buff][buff] = 1;
}
}
if ((current - 1) >= 0) {
if (!visit[current - 1][buff]) {
q.push({ current - 1, buff }); // 현재 내용 - 1개 제거
visit[current - 1][buff] = 1;
}
}
if (!visit[current][current]) {
q.push({ current, current }); // 클립보드 새로 복사
visit[current][current] = 1;
}
}
cnt++;
}
}
int main() {
cin >> N;
q.push({ 1,1 });
visit[1][1] = 1;
bfs(1);
cout << cnt;
}
