글 읽기 - 배열의 할당 위치

spacein1001 3년 전 0

64행에 visit = new boolean[N+1]; 부분이 30행에 있었는데 BFS()가 i=1일때만 돌아가고 멈춰버리더군요 ..

visit이 모두 true로 바뀌어서 i=2부터 돌아가지 않는다는 것은 알겠는데 왜 64행에서는 정상적으로 작동하는지 궁금합니다.

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

public class step3_플로이드와샬_BFS_1389 {
	static int N,M;
	static ArrayList<Integer>[] list;
	static boolean[] visit;
	
	static class Pair{ // 쌍을 만드는데 x는 사람, cnt는 경로의 수를 뜻함
		int x,cnt;
		public Pair(int x,int cnt) {
			this.x = x;
			this.cnt = cnt;
		}
	}
	
	static Queue<Pair> q = new LinkedList<>();
	static int Min = Integer.MAX_VALUE;
	static int result=0,who=0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 사람 수
		M = Integer.parseInt(st.nextToken()); // 관계 수
		
		list = new ArrayList[N+1]; // 사람이 1~N까지 
		
		for(int i=0;i<=N;i++) {
			list[i] = new ArrayList();
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[a].add(b);
			list[b].add(a);
		}
		
		for(int i=1;i<=N;i++) {
			
			q.add(new Pair(i,0)); // i를 넣고 cnt는 0으로 시작
			result = 0;
			
			BFS();
			
	//		bw.write(result+" ");
			
			if(Min > result) {
				Min = result; // 최솟값을 찾고 그 사람의 index를 찾으면 됨
				who = i; // who는 result값이 최소가 된 사람
			}
		}
		
		bw.write(who+" ");
		bw.flush();
	}
	
	public static void BFS() {
		visit = new boolean[N+1]; // 이부분이 밖에 있어서 안돌아갔었는데 이유는 ??
		
		while(!q.isEmpty()) {
			Pair p = q.poll();
			result += p.cnt; // result에 cnt가 증가하는 값들을 모두 더해 Min을 계속 갱신해야함
			
			visit[p.x] = true; // p.x는 Pair의 x값으로 사람의 번호를 뜻함
			
			for(int i=0;i<list[p.x].size();i++) {
				int nx = list[p.x].get(i); // nx = x와 연결된 사람 i라는 뜻
				
				if(!visit[nx]) {
					q.add(new Pair(nx,p.cnt+1)); // nx를 추가하면서 cnt를 한번씩 증가시켜나감
					visit[nx] = true;
				}
			}
			//for문 종료
		}
		//while문 종료
	}
}

chogahui05 3년 전 0

visit = new boolean[N+1]이자나요

BFS를 돌릴 때, 저 문장이 수행되면 visit가 boolean 배열 객체의 참조값이 됩니다. 즉, 새로 생성된 boolean 배열을 가리키게 되는 거죠.

그리고 저 경우에 어떻게 초기화가 되는지는 공식 문서 찾아보세요.

30번째 줄에 visit = new boolean[N+1]이 있으면

본 로직이 30번째 줄 밑에 있고 30번째 줄 다음에 본 로직이 수행되는데, 당연하게도 제대로 수행이 되지 않겠죠?

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

문제

문제

출처

ICPC

배열의 할당 위치

spacein1001 3년 전 0

chogahui05 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말