글 읽기 - 리스트와 배열로 각각 구현했는데, 질문있습니다.

kkb910711 7년 전 0

먼저 배열로 구현했을 때 맞았습니다.

리스트로도 한번 풀어보고 싶어서 비슷한 방식으로 구현했는데, 리스트로 구현했을 때는 틀렸다고 나오네요.. 어디가 잘못된건지 모르겠네요...

예제는 맞다고 출력하고, 질문 검색에 있는 예외들 전부 넣어봤는데, 제대로 출력했습니다..뭐가 문제인지 모르겠네요...

import java.util.*;

public class Main {
	public static void main(String argv[]){
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		int nV = Integer.parseInt(str.split(" ")[0]);
		int nE = Integer.parseInt(str.split(" ")[1]);
		int start = Integer.parseInt(str.split(" ")[2]);
		
        //int map[][] = new int[nV+1][nV+1]; //배열로 구현
		ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>(); //리스트로 구현
		boolean visit1[] = new boolean[nV+1];
		boolean visit2[] = new boolean[nV+1];
		for(int i=0; i<nV+1; i++){
			map.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<nE; i++){
			str = scan.nextLine();
			int a = Integer.parseInt(str.split(" ")[0]);
			int b = Integer.parseInt(str.split(" ")[1]);
			
            //map[a][b] = 1; //배열로 구현
            //map[b][a] = 1; //배열로 구현
			map.get(a).add(b); //리스트로 구현
			map.get(b).add(a); //리스트로 구현
		}
		
		dfs(map, visit1, start);
		System.out.println();
		bfs(map, visit2, start);
	}
	
    //배열로 구현한 dfs
	//static void dfs(int map[][], boolean visit[], int start){
	//	visit[start] = true;
	//	System.out.print(start + " ");
		
	//	for(int i=1; i<map[start].length; i++){
	//		if(map[start][i]==1 && visit[i]==false){
	//			dfs(map, visit, i);
	//		}
	//	}
	//}
	
	//배열로 구현한 bfs
	//static void bfs(int map[][], boolean visit[], int start){
	//	Queue<Integer> q = new LinkedList<Integer>();
	//	q.offer(start);
		
	//	while(!q.isEmpty()){
	//		int tmp = q.poll();
	//		visit[tmp] = true;
	//		System.out.print(tmp + " ");
			
	//		for(int i=1; i<map[tmp].length; i++){
	//			if(map[tmp][i] == 1 && visit[i] == false){
	//				q.offer(i);
	//				visit[i] = true;
	//			}
	//		}
	//	}		
	//}
    
	//리스트로 구현한 dfs
	static void dfs(ArrayList<ArrayList<Integer>> map, boolean visit[], int start){
		visit[start] = true;
		System.out.print(start + " ");
		
		for(int i=0; i<map.get(start).size(); i++){
			if(visit[map.get(start).get(i)] == false){
				dfs(map, visit, map.get(start).get(i));
			}
		}
	}
    
	//리스트로 구현한 bfs
	static void bfs(ArrayList<ArrayList<Integer>> map, boolean visit[], int start){
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(start);
		
		while(!q.isEmpty()){
			int tmp = q.poll();
			visit[tmp] = true;
			System.out.print(tmp + " ");
			
			for(int i=0; i<map.get(tmp).size(); i++){
				if(visit[map.get(tmp).get(i)] == false){
					q.offer(map.get(tmp).get(i));
					visit[map.get(tmp).get(i)] = true;
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

리스트와 배열로 각각 구현했는데, 질문있습니다.

kkb910711 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말