[SWEA/D4] 1238. Contact - JAVA 자바

• 121ms
• BFS 인접행렬

시작 index부터 방향 그래프로 연결된 index로 계속해서 가지처럼 뻗어나가며 마지막의 도달하는 index를 출력하는 문제이다. 마지막에 도달하는 index가 여러 개일 경우 가장 큰 index를 출력한다.

 

번호index와 도달하는 시간time을 저장할 수 있는 node 클래스를 만들어 BFS를 진행하며 큐가 비어 종료하기 직전 시간과 일치한 시간을 가진 node 중 index가 가장 큰 node를 출력하는 방식으로 구현하였다.

 

시작값start을 먼저 먼저 큐에 담고 방문처리한 후, 방향그래프인 graph[start][]와 연결된 i를 찾아 방문처리 및 시간을 하나 증가하여 큐에 넣어주며 가지가 끝날 때까지 반복해준다. 큐가 종료하기 직전에 저장한 lastTime과 일치하는 node의 time을 찾아 가장 큰 index를 저장해준다.

 

# 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
    int index;
    int time;

    public Node(int index, int time) {
        this.index = index;
        this.time = time;
    }
}

public class Solution {

    static int n, start, lastTime, result;
    static Node[] nodes = new Node[101];
    static boolean[][] graph = new boolean[101][101];
    static Queue<Node> q = new ArrayDeque<>();
    static boolean[] visited = new boolean[101];

    public static void bfs() {
        visited[start] = true;
        nodes[start] = new Node(start, 0);
        q.offer(nodes[start]);
        while (!q.isEmpty()) {
            Node now = q.poll();

            for (int i = 1; i <= 100; i++) {
                if(!visited[i] && graph[now.index][i]) {
                    // 방문하지 않았고, index가 전화 걸 수 있는 번호 찾기
                    visited[i] = true;
                    nodes[i] = new Node(i, now.time + 1);
                    q.offer(nodes[i]);    
                    lastTime = now.time + 1;
                }
            }
        }

        for(int i = 1; i<=100; i++) {
                if(nodes[i] != null && nodes[i].time == lastTime) {
                    result = Math.max(result, i);
                }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        for (int t = 1; t <= 10; t++) {
            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            start = Integer.parseInt(st.nextToken());

            nodes = new Node[101];
            for(boolean[] col : graph)
                Arrays.fill(col, false);
            Arrays.fill(visited, false);
            result = 0;
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n/2; i++) {
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                graph[from][to] = true;
            }
            bfs();
            sb.append('#').append(t).append(' ').append(result).append('\n');
        }
        System.out.println(sb);
    }
}

코드에 대한 피드백은 언제나 환영입니다🧚🏻‍♀️