프로그래머스. 리틀 프렌즈 사천성

https://programmers.co.kr/learn/courses/30/lessons/1836

코딩테스트 연습 - 리틀 프렌즈 사천성

 

상당히 푸는데 오래 걸린 문제였다.

처음에 해가 여러가지인 경우 알파벳 순으로 먼저인 문자열 리턴하는것과 bfs 탐색을 한다는것은 금방 생각했고 구현했는데 틀렸다.

 

테스트케이스를 넣어보면서 틀린점을 발견했는데 bfs 탐색을 할때 보통의 bfs 알고리즘이라면

하나의 좌표에서 이동 가능한 모든 좌표로 동시에 이동하고 이동했음을 표시하고, 이동한 좌표는 다시 방문하지 않도록 한다.

여기서가 문제였는데 이 문제에서는 만약 하나의 좌표에서 이동하고 이동한 곳을 방문표시하면 다른 좌표에서 그 좌표를 거쳐서 목적지에 도달할 가능성을 차단해버린다. 

 

예를들어 아래와 같이 먼저 이동하면 

아래처럼 한번 꺾어서 이동할수 있는 가능성이 차단된다. 

 

이렇게 문제점을 해결하고 제출했는데 이번에는 시간초과가 났다.

여기서 고민하다가 하루가 지났다..

결국 다른 분들 코드를 봤는데 시간초과과는 다음과 같이 해결했다.

 

내 기존 코드는 큐에서 좌표를 뽑고, 다음 좌표를 계산해서 큐에 넣고, 다시 좌표를 뽑는 과정에서 예외 검사를 했다.

즉 일단 모든 다음 좌표를 큐에 모두 넣고 뽑을때 예외사항을 검사했는데,

먼저 예외검사를 하고 적합한 좌표만 큐에 넣도록 수정했다.  

 

또 이전 코드는 방문여부를 확인하는 배열을 bfs 탐색할때마다 초기화해줬는데, 

방문여부 확인 배열이 필요가 없고, 그냥 다음 좌표가 이전 좌표로 돌아가는 경우만 아니면 된다.

여기서 방문여부 확인하는 배열의 유무 때문에 시간초과가 난 것 같다.  

 

 

 

---

2022.01.07 

 

다시 풀어봤는데 또 틀림.

어디가 틀렸나 계속 찾아봤는데 

while문 돌리면서 지워지는 문자를 answer에 추가하다가 

모든 종류의 문자들이 answer에 추가됐다면 break해줘야함.

 

틀린 코드:

while(true)
{
    bool possible = false;
    for(int i = 0; i < tmp.size(); i++)
    {
        if(mark[i]) continue;
        if(bfs(map[tmp[i]].first, map[tmp[i]].second))
        {
            answer += tmp[i];
            mark[i] = true;
            possible = true;
            break;
        }
    }
    if(!possible) break;
}

 

맞은 코드:

bool impos = false;
vector<bool> mark(tmp.size(), false);
while(true)
{
    bool possible = false;
    for(int i = 0; i < tmp.size(); i++)
    {
        if(mark[i]) continue;
        if(bfs(map[tmp[i]].first, map[tmp[i]].second))
        {
            answer += tmp[i];
            mark[i] = true;
            possible = true;
            break;
        }
    }
    if(!possible) { impos = true; break; }
    if(answer.size() == tmp.size()) {impos = false; break;}
}

if(impos) answer = "IMPOSSIBLE";
return answer;