Record for Success

문제 출처: 백준 온라인 저지

문제 설명

🔎 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.

단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.

- 비용은 대칭적이지 않다. 
- 즉, W[i][j] 는 W[j][i]와 다를 수 있다.
- 모든 도시간의 비용은 양의 정수이다.
- W[i][i]는 항상 0이다.
- 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

위 예제를 그림으로 나타내면 이와 같다.

여기서 정답인 경로는 여러가지가 존재하지만, 하나만 꼽아보자면 2 ➡ 0 ➡ 1 ➡ 3 ➡ 2 순으로 순회할 경우 총 비용이 35로 최소가 된다.

이런 방식으로 접근을 한다면 그래프를 순회하는 알고리즘 중 하나를 사용해야 한다는 것을 알 수 있다.

나는 여기서 DFS를 이용하기로 했다.

<정답 코드>

def dfs(x, val, depth=1):
    global cost
    global first
    global n

    if depth == n:
        for nx, _cost in graph[x]:
            if nx == first:
                cost = min(cost, val+_cost)
        return

    if visit[x]:
        return

    visit[x] = True

    for nx, _cost in graph[x]:
        if not visit[nx]:
            dfs(nx, val+_cost, depth+1)
            visit[nx] = False


n = int(input())
graph = [[] for _ in range(n)]
cost = float('inf')

for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        if i == j or arr[j] == 0: continue
        graph[i].append((j, arr[j]))

for i in range(n):
    visit = [False] * n
    first = i
    dfs(i, 0)

print(cost)

우선은 2차원 배열형태로 접근하는게 아니라 그래프 형태로 접근하기 위해서 입력을 그래프 형식으로 전환한 뒤 시작하였다.

접근은 아래와 같다.

1. 모든 도시에서 한번씩 시작하며 dfs를 순회한다.
2. dfs를 순회할 때는 시작 지점인 first를 기록하고 시작한다.
3. 한번 방문하고 함수를 빠져나오게 될 때 visit을 초기화 해주어 모든 경로를 탐색할 수 있게 한다.
4. dfs의 depth가 n이 될 때 까지 recursion하며, depth가 n일 때 현재 도시에서 first로 갈 수 있으면 cost를 업데이트 해준다.

처음에는 DP나 다익스트라 문제인 줄 알았다.

하지만, 모든 도시를 다 방문해야하고 출발 지점이 정해져있지 않았으며 한번 방문한 도시는 다시 방문할 수 없었기에 dfs를 통해 접근해야 한다는 사실을 깨달았다.

문제 출처: 프로그래머스

문제 설명

🔎메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다.

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

전형적인 dfs, bfs 문제였다.

maps와 그 원소들의 길이가 100이었고, 값이 'X' 또는 1~9사이 숫자로 조건도 완벽했다.

우선은 조금 더 친한 dfs를 통해서 문제를 해결하려고 시도했으나, 런타임 에러와 실패가 많이 떴다.

탐색 과정을 시각화해서 살펴봐도 내가 테스트한 케이스들에서는 잘 작동했다. 아마 탈출 조건에서 에러가 발생한 것 같지만, 아직까지 원인은 발견하지 못했다..

<틀린 코드 보기>

def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0]*c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def dfs(x, y, val):
        if visit[x][y] or maps[x][y] == 'X':
            return

        visit[x][y] = 1
        flag = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] != 'X' and not visit[nx][ny]:
                flag += 1
                dfs(nx, ny, val + int(maps[nx][ny]))

        if flag == 0:
            answer.append(val)


    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                dfs(i, j, int(maps[i][j]))
    
    
    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

그래서 bfs로 방향을 틀어 문제를 푸니까 맞았다.

<정답 코드>

from collections import deque
def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0] * c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def bfs(x, y):
        if visit[x][y] or maps[x][y] == 'X':
            return

        q = deque()
        q.append((x, y))
        visit[x][y] = 1
        val = 0
        while q:
            cx, cy = q.popleft()
            val += int(maps[cx][cy])

            for i in range(4):
                nx, ny = cx+dx[i], cy+dy[i]
                if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] and maps[nx][ny] != 'X':
                    q.append((nx, ny))
                    visit[nx][ny] = 1

        return val

    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                life = bfs(i, j)
                if life:
                    answer.append(life)

    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

접근은 아래와 같다.

1. 탐색이 좀 더 편하도록 maps의 원소를 list로 변환한다.
2. 문제에서 대각선을 포함하지 않았기 때문에, 대각선 방향을 제외한 4가지 방향을 dx, dy배열로 준비한다.
3. X가 아닌 지역에서 bfs를 수행한다. bfs를 마친 결과를 answer배열에 업데이트 한다.
4. answer 배열을 오름차순으로 정렬하여 return한다.

다시 보니 코드가 그렇게 깔끔하게 작성된 것 같진 않다. 

중복해서  점검하는 부분도 있는 것 같고, 좀 더 짧게 작성할 수 있었을 것 같다. 

문제 출처: 프로그래머스 ( https://school.programmers.co.kr/learn/courses/30/lessons/49189 )

문제 설명

🔎n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항
1. 노드의 개수 n은 2 이상 20,000 이하입니다.
2. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
3. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

해당 문제는 전형적인 그래프 최단거리를 구하는 문제로, bfs를 사용할 줄 알면 간단하게 풀 수 있는 문제이다.

다만, 문제의 설명에 연결되지 않은 1번 노드에 연결되지 않은 노드가 존재할 수 있다는 문구가 있었으면 조금 더 좋았을 것 같다.

<정답 코드>

from collections import deque
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    for start, end in edge:
        graph[start].append(end)
        graph[end].append(start)
    
    dist = [float('inf')] * (n+1)
    visited = [False] * (n+1)
    
    dist[1] = 0
    q = deque()
    q.append(1)
    while q:
        cur = q.popleft()
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for x in graph[cur]:
            if dist[x] > dist[cur] + 1:
                dist[x] = dist[cur] + 1
                q.append(x)
                

    target = 0
    for i in dist[1:]:
        if i != float('inf') and target < i:
            target = i
    
    answer = dist.count(target)
    
    
    return answer

접근 방법은 아래와 같다.

1. 주어진 파라미터를 통해 그래프를 생성한다.

2. 1번 노드를 출발점으로 지정하여, 그래프를 탐색한다. 탐색한 깊이에 따라 거리를 업데이트 해준다.

3. 거리 리스트에서 inf가 아닌 최대 값을 도출하고 이것을 count한다.

처음에는 max(dist)를 target으로 설정하고 진행하였다. 하지만 테스트 2번 예시를 통해 앞서 언급한 방문 불가 노드가 있다는 사실을 깨닫고 위와 같이 수정하였다.

<테스트 2>