[Algorithm]Baekjoon 14226번 : 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

 

 

struct Node
{
    int displayNum;
    int boardNum;
    int depth;
 
    Node() {};
    Node(int _displayNum, int _boardNum, int _depth) : displayNum(_displayNum), boardNum(_boardNum), depth(_depth) {};
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int s = 0;
    int answer = 1000000000;
 
    map<pair<int, int>, bool> visited;
 
    queue<Node> q;
    q.push(Node(1, 0, 0)); // 화면, 보드, 트리깊이
    visited[{1, 0}] = true;
    cin >> s;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curDisplayNum = curNode.displayNum;
        int curBoardNum = curNode.boardNum;
        int curDepth = curNode.depth;
 
        if (curDisplayNum == s)
        {
            answer = curDepth;
            break;
        }
 
        // 첫번째 작업
        int dn1 = curDisplayNum; // 그대로
        int bn1 = curDisplayNum; // 화면->보드 복사
 
        // 두번째 작업
        int dn2 = curDisplayNum + curBoardNum; // 화면 + 보드
        int bn2 = curBoardNum; // 그대로
 
        // 세번째 작업
        int dn3 = curDisplayNum - 1; // 1개삭제
        int bn3 = curBoardNum; // 그대로.
 
        if (dn1 <= s && !visited[{dn1, bn1}])
        {
            visited[{dn1, bn1}] = true;
            q.push(Node(dn1, bn1, curDepth + 1));
        }
 
        if (dn2 <= s && !visited[{dn2, bn2}] )
        {
            visited[{dn2, bn2}] = true;
            q.push(Node(dn2, bn2, curDepth + 1));
        }
 
        if (dn3 >= 0 && !visited[{dn3, bn3}])
        {
            visited[{dn3, bn3}] = true;
            q.push(Node(dn3, bn3, curDepth + 1));
        }
    }
 
    cout << answer;
}

각 간선의 가중치는 1인 기본 BFS문제이고, 대신 각 정점은 화면의 이모티콘갯수가 아니라, 화면의 이모티콘개수 + 보드의 이모티콘개수이다.

 

즉, 방문체크를 할 때 두 값을 셋트로해서 검사해야한다.

방문체크용 자료구조를 map으로 했기 때문에 따로 사이즈를 처음에 할당할 필요는 없다.bool의 default는 false이기 때문에 위처럼 코드를 짜는게 가능하다.

푸쉬여부를 체크할때의 dn1, dn2값범위 체크는 s이하이면 된다. 보통 이런문제 풀때 그냥 최대값으로(이번문제같은경우 1000) 잡고 검사하기도 하는데, 물론 이렇게해도 통과가 되기는 한다.

다만 조금이라도 시간을 줄일 수 있다면 줄이는게 맞으니 s까지만 검사하도록 하자.

최대값으로 할 경우 12ms가 나오고 s까지만 하면 8ms가 나온다.