BOJ_15971_두 로봇 (Java, C++)

[Gold IV] 두 로봇 - 15971

문제 링크

성능 요약

메모리: 81880 KB, 시간: 444 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 5일 22:05:56

문제 설명

2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.

새로 발견된 동굴을 조사하기 위해 동굴 탐사 로봇 두 대를 이용하기로 하였다. 두 로봇은 어떤 시점이 되면 각자가 획득한 정보를 공유하기 위해 통신을 해야 한다. 두 로봇이 서로 통신을 하기 위해서는 동굴 내의 같은 통로 위에 위치해야만 한다. 참고로 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주한다.

<그림 1> 동굴 내부를 간략히 표현한 그림

<그림 1>은 방이 9개인 동굴 내부를 간략하게 나타낸 예이다. <그림 1>에서 방은 원으로 표현되어 있으며 원 안의 수는 방 번호이다. 8개의 통로는 두 원 사이의 선분으로 표시되어 있으며 그 위의 정수 값이 통로의 길이이다. 예를 들어, 5번 방과 9번 방 사이에 길이가 6 인 통로가 있음을 알 수 있다. 만약 두 로봇이 1번 방과 9번 방에 위치해 있다면, 각각 2번 방과 5번 방으로 이동한 후 통신할 수 있으며 이때 이동한 거리의 합은 14로 최소이다.

동굴 내의 통로에 대한 정보와 두 로봇의 현재 위치가 입력으로 주어질 때, 서로 통신하기 위해 이동해야 하는 거리의 합의 최솟값을 계산하는 프로그램을 작성하시오.

동굴의 각 통로는 양 끝에 위치한 두 방의 번호와 그 길이로 주어진다. 두 로봇의 위치는 방 번호로 주어진다.

입력

표준 입력으로 동굴의 방의 개수 N과 두 로봇이 위치한 방의 번호가 세 개의 양의 정수로 공백으로 분리되어 첫 줄에 주어진다. 이후 동굴의 통로 N-1개가 한 줄에 하나씩 주어진다. 각 통로는 세 개의 양의 정수로 공백으로 분리되어 한 줄에 주어지며, 앞 두 정수는 통로의 양 끝에 위치한 방의 번호를, 세 번째 정수는 그 통로의 길이를 의미한다.

출력

표준 출력으로 두 로봇이 서로 통신하기 위해 현재 위치에서 이동해야 하는 거리의 합의 최솟값을 정수로 출력한다.

문제 풀이

전체 거리에서 최대 간선 값을 빼주었다. 주의할 점은 서브태스크에서 시작점이 같거나 정점이 1개밖에 없으면 0을 출력해줘야하고 이미 한 칸 건너 로봇이 있으면 움직일 필요 없으므로 이때도 0이다.

C++코드에서 배운 점

• const - 반복하면서 요소를 변경하지 않겠다는 의미, 실수로 데이터를 수정하는 것을 방지

• Node& - 참조자(reference)를 사용(직접참조). &가 없으면 매번 복사가 일어나 성능이 저하된다. &를 사용하면 원본 데이터를 직접 참조하여 성능이 향상된다

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	class Node{
		int to;
		int W;
		public Node(int to, int W){
			this.to = to;
			this.W = W;
		}
	}
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, robot1, robot2, first, second, w, totalD, maxW;
	static ArrayList<Node>[] map;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		robot1 = Integer.parseInt(st.nextToken());
		robot2 = Integer.parseInt(st.nextToken());

		if(N == 1 || robot1 == robot2) {
	        bw.write("0");
	        bw.flush();
	        bw.close();
	        br.close();
	        return;
	    }
		
		map = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			map[i] = new ArrayList<Node>();
		}
		
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine());
			first = Integer.parseInt(st.nextToken());
			second = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			map[first].add(new Node(second, w));
			map[second].add(new Node(first, w));
		}
		
		visited = new boolean[N+1];
		totalD = 0;
		maxW = 0;
		
		dfs(robot1, robot2);
		bw.write(String.valueOf(totalD - maxW));
		bw.flush();
		bw.close();
		br.close();
	}

	private boolean dfs(int start, int end) {
		if(start == end) {
			return true;
		}
		
		visited[start] = true;
		
		for(Node n : map[start]) {
			if(!visited[n.to]) {
				int prevMax = maxW;
				maxW = Math.max(maxW, n.W);
				totalD += n.W;
				
				if(dfs(n.to, end)) return true;
				
				// 백트래킹
				totalD -= n.W;
				maxW = prevMax;				
			}
		}
		
	    // 경로를 못 찾았을 때 백트래킹 및 초기화
		visited[start] = false;
		maxW = 0;
		return false;
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct Node {
    int to;
    int W;
    Node(int to, int W) : to(to), W(W) {}
};

vector<vector<Node>> board;
vector<bool> visited;
int N, robot1, robot2, totalD, maxW;

bool dfs(int start, int end) {
    if (start == end) return true;

    visited[start] = true;

    for (const Node& n : board[start]) {
        if (!visited[n.to]) {
            int prevMaxW = maxW;
            maxW = max(maxW, n.W);
            totalD += n.W;

            if (dfs(n.to, end)) return true;

            maxW = prevMaxW;
            totalD -= n.W;
        }
    }

    visited[start] = false;
    maxW = 0;
    return false;
}

void solve() {
    cin >> N >> robot1 >> robot2;
    if (N == 1 || robot1 == robot2) {
        cout << 0 << "\n";
        return;
    }

    board.resize(N + 1);
    visited.resize(N + 1, false);

    for (int i = 0; i < N - 1; i++) {
        int first, second, w;
        cin >> first >> second >> w;
        board[first].push_back(Node(second, w));
        board[second].push_back(Node(first, w));
    }

    totalD = 0;
    maxW = 0;

    dfs(robot1, robot2);
    cout << totalD - maxW << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}