글 읽기 - 7% 시간초과, 어찌해야할지 모르겠습니다ㅠㅠ

physiqueloper 2년 전 0

값 찾으면 탈출하게끔 해놨는데도 시간초과가 뜨네요ㅠㅠㅠ

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Gold_Impl_13023 {
	static int n;
	static int m;
	static int[][] way;
	static int[] visited;
	static int[] node;

	static boolean find = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);

		node = new int[n];
		for (int i = 0; i < n; i++) {
			node[i] = i;
		}

		way = new int[n][n];
		for (int i = 0; i < m; i++) {
			String[] temp = br.readLine().split(" ");
			way[Integer.parseInt(temp[0])][Integer.parseInt(temp[1])] = 1;
			way[Integer.parseInt(temp[1])][Integer.parseInt(temp[0])] = 1;
		}

		for (int i = 0; i < node.length; i++) {
			visited = new int[n];
			int depth = 0;
			dfs(i, depth);
			if (find == true) {
				System.out.println(1);
				return;
			}
		}
		System.out.println(0);
	}

	static void dfs(int fr, int depth) {
		visited[fr] = 9;
		depth++;
		if (depth >= 5) {
			find = true;
			return;
		}
		for (int i = 0; i < way.length; i++) {
			if (way[fr][i] == 1 && visited[i] != 9) {
				dfs(i, depth);
			}
		}
	}
}

dldyddlwl 2년 전 0

아래에 있습니다.

way = new int[n][n];
for (int i = 0; i < m; i++) {
    String[] temp = br.readLine().split(" ");
    way[Integer.parseInt(temp[0])][Integer.parseInt(temp[1])] = 1;
    way[Integer.parseInt(temp[1])][Integer.parseInt(temp[0])] = 1;
}
// 아무래도 2차원 배열을 이용하시다보면,
// 주어진 사람과 연결된 사람들을 찾기 위해선, 모든 사람들을 조사해봐야만 알 수 있습니다. 
// => (way[지금 사람][i] == 1인지 검사하기 위해 i는 0~n-1 까지 반드시 탐색해야함)

// 그러다보면, 아무래도 ArrayList가 탐색에 훨씬 유리합니다. ( 연결된 친구들만 add로 저장했으므로, 다른 아이들 탐색 필요 X)

// 아래 같은 방식으로 하면, a와 연결된 사람을 찾을때, graph[a]의 원소들만 탐색하면 되므로, 시간이 절약됩니다. 
static ArrayList<Integer>[] graph;
graph[a].add(b);
graph[b].add(a);

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7% 시간초과, 어찌해야할지 모르겠습니다ㅠㅠ

physiqueloper 2년 전 0

dldyddlwl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말