[프로그래머스] 여행경로 [Level 3] (python 파이썬) [BFS]

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

 

 

 

 

from collections import deque
def solution(tickets):

    d= deque()
    n = len(tickets)
    for i in range(n):
        if tickets[i][0] == "ICN":
            visit = [0 for i in range(n)]
            visit[i] = -1
            d.append([tickets[i][1],tickets[i],visit])
    ans_l = []
    while d:
        d2 = d.popleft()
        current, ans, visit = d2[0], d2[1], d2[2]
        if len(ans) == n+1:
            ans_l.append(ans)
            continue
        for i in range(n):
            if tickets[i][0] == current:
                if visit[i] == 0:
                    new_visit = visit[:]
                    new_ans = ans[:]
                    new_visit[i] = -1
                    new_ans.append(tickets[i][1])
                    d.append([tickets[i][1], new_ans, new_visit])
                    
    ans_l.sort()
    return ans_l[0]

 

 

 

---

 

문제 제한 사항을 보자

 

 

모든 공항은 알파벳 대문자 3글자로 이루어진다.

 

주어진 공항 수는 3개 이상 10000개 이하이다.

 

tickets의 각 행 [a,b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이다.

 

주어진 항공권은 모두 사용해야 한다.

 

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 한다.

 

모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

 

 

 

 

 

코딩 테스트를 풀 때 중요한 점은 무엇일까?

문제 제한 사항을 빠짐없이 모두 사용하는 것이다.

 

출제자가 문제를 낼 때 굳이 필요 없는 정보를 줄 이유는 없다.

 

따라서 문제에 적혀있는 모든 정보는 문제를 풀기 위해 필요한 정보이다.

 

 

 

 

 

 

 

 

 

 

 

---

 

이 문제가 DFS임을 알고 문제를 풀어가는 근거가 무엇일까?

 

위 제한 사항 중 더 중요한 제한 사항은 무엇일까?

 

주어진 항공권은 모두 사용해야 한다.

=> 한번 사용한 항공권은 다시 사용하지 않을 것이다 

=> 방문처리가 필요하다!

 

 

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 한다.

=> 문제 조건을 만족하는 경로가 여러가지 이고 특정 조건으로 정렬이 필요하디

=> 입력값을 직접 수정하며 방문 처리를 할 수 없다 => tickets 값을 직접 수정하며 방문 처리를 할 수 없다.

=> 방문 정보 리스트를 추가로 만들어서 추가로 입력해주어야 한다.

 

 

 

 

 

https://mail-study.tistory.com/41

[백준] 21736번 : 헌내기는 친구가 필요해 [BFS 설명 有]

 

https://mail-study.tistory.com/42

[프로그래머스] 단어 변환 [Level 3] (python 파이썬) [DFS/BFS]

 

 

 

두 글을 보면 DFS의 공통적인 특징과 답을 향해가는 사고과정이 잘 설명되어 있다.

 

 

위의 BFS 설명을 보면 BFS 에는 공통적인 특징이 있다.

 

1. 어느 점을 기준으로 좌표를 이동한다.

= 여행 경로 문제에 따르면 항상 "ICN" 공항에서 출발한다.

= 즉 ICN을 기준으로 좌표를 이동하므로 덱에 ICN으로 시작하는 루트를 넣어 초기화 해준다.

 

2. 이동하면 일련의 로직을 수행한 후 다음 좌표를 덱에 넣어준다. 이때 방문 정보 등, 후처리에 필요한 정보도 같이 넣어준다.

= 여행 경로 문제에 따르면 각 행의 [a,b]는 공항의 출발과 도착점이므로 a,b의 정보와 현재 위치를 보며

   현재 사용할 수 있는 항공권인지를 체크해준다.

 

3. 방문한 좌표에 방문 처리를 해준다.

= 앞서 설명했듯이 가능한 경로가 여러가지 이므로 방문 정보가 추가로 필요하다.

 

 

DFS 문제의 사고과정

 

입력의 제한조건을 잘 보며 모든 경우를 다 살펴봐도 시간복잡도가 초과될지 생각해보자!

 

 

문제가 어떤 정답을 요구하는 가에 따라 어떤 식으로 방문 처리를 해야 할 지 생각해보자!

방문정보가 추가로 필요하므로 visit = [0 for i in range(n)] 으로 방문 리스트를 만들었다.

 

문제가 요구하는 핵심적인 로직을 어떻게 쉽게 짤 지 고민해보자!

여행 경로가 요구하는 핵심적인 로직은, 현재 지점에서 사용할 수 있는 항공권인지를 구분하는 로직이다.

 

 

 

 

---

추가로 필요한 아이디어

 

for i in range(n):

            if tickets[i][0] == current:

위 코드를 보면 항공권을 순서대로 돌면서 

현재 위치에서 사용할 수 있는 항공권이면 다음 행선지로 옮겨간다.

 

위의 방식에서 주의해야 할 점은 무엇일까?

 

바로 for문으로 항공권을 순서대로 돈다는 점이다.

 

 

for문을 사용하면 "순서대로" 접근하기 때문에, 순서에 의존할 수 있는 문제를 초례하게 된다!

 

[[A,C], [A,D]]

만약 위의 순서대로 항공권이 존재하고, 현재 위치가 A일 때

위 코드로 진행하면 무조건 [A,C] 항공권을 선택해 C로 갈 수 밖에 없다.

 

즉 [A,D] 항공권을 먼저 선택하는 경우가 없다는 것이다.

 

 

 

정말 정말 중요!

 

잘 생각해보자.

for문을 돌며 조건을 만족하는 항공권을 찾았을 때 가능한 경우는 2가지 이다.

 

1. break 해서 바로 다음 행선지로 간다.

 

2. 계속 for문을 돌면서, 다른 경우도 접근해본다.

 

 

1번이 안되는 이유는 간단하다.

조건을 만족하는 경우가 여러가지 이므로 바로 다음 행선지로 가면, 다른 경우를 접근할 수 없다.

 

따라서 무조건 2번의 경우로 진행해야 한다.

여기에서 중요한 점이 존재한다.

 

    while d:

        d2 = d.popleft()

        current, ans, visit = d2[0], d2[1], d2[2]

우리는 현재 while문 안에서 무슨 정보를 가지고 있는가?

 

우리는 현재 위치, 지금까지의 경로, 사용한 항공권의 정보를 가지고 있다.

 

 

 for i in range(n):

            if tickets[i][0] == current:

                if visit[i] == 0:

                    visit[i] = -1

 

그런데 만약 위처럼,

현재 위치에서 갈 수 있는 항공권을 찾아서

항공권을 사용처리를 해버리면 어떻게 될까?

 

for문의 다음 항공권을 확인할 때 이미 현재 위치에서 항공권을 사용해버린 경우가 돼버린다.  

여러 가지 경우를 생각해 visit 값을 넘겨주었지만,

for문을 고려하면 현재 위치에서도 여러가지 visit의 경우가 필요하다는 것이다.

 

따라서

for i in range(n):

            if tickets[i][0] == current:

                if visit[i] == 0:

                    new_visit = visit[:]

                    new_ans = ans[:]

                    new_visit[i] = -1

                    new_ans.append(tickets[i][1])

 

만족하는 항공권을 찾으면, 현재 사용한 항공권 정보를 복사하여 새로 만들어 넣어준다.

 

위의 방식을 사용하면, 현재 위치에서의 항공권 정보가 사용 가능한 항공권을 찾아도 변경되지 않을 것이다.

즉 각각의 항공권에도 독립적으로 작용할 수 있다는 것이다.

 

 

 

---

이번 문제에서는 위의 아이디어가 추가적으로 필요했었다.

 

 

앞서 말했지만 DFS를 풀기 위해서는 

 

 

문제가 어떤 정답을 요구하는 가에 따라 어떤 식으로 방문 처리를 해야 할 지 생각해보자!

문제가 요구하는 핵심적인 로직을 어떻게 쉽게 짤 지 고민해보자!

 

위와 같이 여러가지 방법을 생각해내야 한다.

 

이번 문제에서는 

정답이 요구하는 조건에 따라 방문 정보를 리스트로 만들어 덱에 입력해주었다.

문제가 요구하는 로직을 고려해서 방문 정보를 복사해서 새로 만들어 넣어주었다.

 

 

 

위처럼 DFS 문제를 풀 때는 공통적인 부분을 잘 고려하고

 

잘 고려했다면

 

문제마다 생각해야 하는 조건과 아이디어를 잘생각해보자!!