[BOJ / 백준] 15971 두 로봇 (G4^ / DFS) - Python

링크

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

 

 

 

 

문제 해석

N개의 방이 존재하고, 통로는 N-1개 존재한다.
두 로봇 간에 통신이 필요하고, 통신을 위해서는 로봇 사이에 1개의 통로만 존재해야 한다.
통신을 하기 위해 두 로봇이 이동해야 하는 최단 거리는?

 

입력
첫 번째 줄 : n, a, b
  n : 방 개수
  a : 1번 로봇 위치
  b : 2번 로봇 위치 

나머지 줄 : s, e, d
  s : 시작점
  e : 끝점
  d : 길이


출력
로봇이 서로 통신하기 위해 현재 위치에서 이동해야하는 거리합의 최솟값

 

 

 

 

풀이 & 코드 해석

bfs나 dfs와 같은 그래프 탐색 기법을 사용하면 풀 수 있는 문제입니다.

 

저는 dfs를 통해 a부터 끝까지 탐사하면서 지나간 통로의 길이를 배열에 저장해두고, b에 도달한다면 (지금까지 지나간 모든 통로의 합 - 가장 긴 통로)를 정답으로 출력하려고 했습니다.

 

 

 

 

코드

import sys
sys.setrecursionlimit(10**6)


def dfs(idx, arr):
    global b, ans

    v[idx] = True

    if idx == b:
        arr.sort()
        ans = sum(arr) - arr[-1]
        return

    for nxt, dis in graph[idx]:
        if v[nxt] == True:
            continue

        arr.append(dis)
        dfs(nxt, arr)
        arr.pop()


n, a, b = list(map(int, input().split()))
v = [False] * (n + 1)
ans = 0

graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    s, e, d = list(map(int, input().split()))

    graph[s].append([e, d])
    graph[e].append([s, d])

if a == b:
    print(0)
    exit()

dfs(a, [])
print(ans)

 

 

 

 

발생한 문제 & 해결 방안

1)

풀이 시 40%에서 틀리는 부분이 있었다.

만약 두 로봇이 같은 위치에 있는 경우에는 어떻게 해야 하는가에 대한 예외처리를 하지 않아 발생한 문제였다.

 

2)

로봇의 위치가 하나의 통로만 가지고 있는 경우에도 동일하게 모든 통로를 더해서 가장 긴 통로를 빼는 방식으로 해결이 되는데 괜히 예외처리하다가 틀렸다.  

정신 차리고 문제 풀어야겠다.

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java