[백준] 1325 : 효율적인 해킹 - JAVA

문제분석

Troubleshooting

public class hacking47 {
static ArrayList<Integer>[] info;
static int[] visited;
static int severalMax;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		List<Integer> answer = new ArrayList<>();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int max = 0;
		info = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			info[i] = new ArrayList<>();
		}
		visited = new int[N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			info[B].add(A);
		}
		for(int i=1; i<N+1; i++) {
			visited[i] =1;
			int canHackingCount = BFS(i);
			if(max == canHackingCount) answer.add(i);
			else if(max < canHackingCount) {
				answer.clear();
				answer.add(i);
			}
			for(int j=0; j<N+1; j++) {
				visited[j] =0;
			}
		}
		for(int i=0; i<answer.size(); i++) {
			System.out.print(answer.get(i)+ " ");
		}
	}
	
	public static int BFS(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		while(!queue.isEmpty()) {
			int nowComputer = queue.poll();
			for(int nearComputer : info[nowComputer]) {
				if(visited[nearComputer] == 0) {
					queue.add(nearComputer);
					visited[nearComputer] = visited[nowComputer]+1; //문제
				}
			}
			severalMax = visited[nowComputer]+1;
		}
		return severalMax;
	}
}

문제

예제1에 대해서 '1 2'가 답으로 나와야하는데 '5'가 나왔다.

원인

다음 노드 값에 현재 노드 값+1 을 넣는게 아니라(즉 depth를 구하는게아니라), 새로운 노드에 방문할때마다 계속 +1한 값을 넣는것이다.(즉 방문할수있는 노드 개수를 구하는것이다)

해결

visited[nearComputer] = visited[nowComputer]+1; -> severalMax++; 수정

Troubleshooting 2

import java.util.*;
import java.io.*;

public class Main {
static ArrayList<Integer>[] info;
static int[] visited;
static int severalMax;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		List<Integer> answer = new ArrayList<>();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int max = 0;
		info = new ArrayList[N+1];
		for(int i=1; i<N+1; i++) {
			info[i] = new ArrayList<>();
		}
		visited = new int[N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			info[B].add(A);
		}
		for(int i=1; i<N+1; i++) {
			severalMax = 1;
			int canHackingCount = BFS(i);
			if(max == canHackingCount) {
				answer.add(i);
			}
			else if(max < canHackingCount) {
				answer.clear();
				answer.add(i);
				max = canHackingCount;
			}
			for(int j=0; j<N+1; j++) {
				visited[j] =0;
			}
		}
		for(int i=0; i<answer.size(); i++) {
			System.out.print(answer.get(i)+ " ");
		}
	}
	
	public static int BFS(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		while(!queue.isEmpty()) {
			int nowComputer = queue.poll();
			for(int nearComputer : info[nowComputer]) {
				if(visited[nearComputer] == 0) {
					queue.add(nearComputer);
					severalMax++;
				}
			}
		}
		return severalMax;
	}
}

문제

시간초과가 났다.

원인

해결