[JAVA] 백준 1240번 - 노드사이의 거리

안녕하세용 오랜만에 방학맞이로 다시 백준 스터디 시작하네요
1240번: 노드사이의 거리 (acmicpc.net)

1240번: 노드사이의 거리

 

---

 

package baekjoon;
import java.util.*;

public class b1240 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n, m, row, col, cost, res, start, end;
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		List<Integer> tree = new ArrayList<>();
		
		int arr[][] = new int[n][n];
		Arrays.fill(arr, 0);
		
		for(int i = 0 ; i < n ; i++)
		{
			row = sc.nextInt();
			col = sc.nextInt();
			cost = sc.nextInt();
			arr[row][col] = cost;
			arr[col][row] = cost;
			tree.add(row);
			tree.add(col);
		}
		Set<Integer> Tree = new HashSet<Integer>(tree);
		List<Integer> newTree = new ArrayList<Integer>(Tree);
		
		for(int i = 0 ; i < m ; i++)
		{
			start = sc.nextInt();
			end = sc.nextInt();			
			res = 999999;
			
			for(int j : newTree)
			{
				for(int k = 0 ; k < )
			}
		}	
	}
}

아무 생각없이 이런 식으로 접근하고 있었는데
삼중 포문 쓰다가 이건 아닐 거 같다는 생각 들어서 다시 계속 써보다가 제자리걸음인 거 같아서 구글링해봤는데
구글링 하다가 든 생각이 제가 제대로 탐색을 하는 코드를 쓰고 있지 않았어서 반성했습니다
 
구글링하다가 배운 거
StringTokenizer
StringTokenizer 변수명 = new StiringTokenizer(문자열,구분자,true/false); //true -> 구분자도 토큰으로 넣게 됨,  default는 false
[JAVA 자바] StringTokenizer 클래스로 문자열 분리하기! split 비교. (tistory.com)

[JAVA  자바] StringTokenizer 클래스로 문자열 분리하기! split 비교.

 
배운 거 2
자바에서 큐 처음 써봐서 몰랐는데 
삽입할때 add, offer(add는 큐 꽉찼을때 에러발생, offer는 값 추가 실패시 false 반환 이두개 차이점 있고 나머지는 같음)
제거할때 remove, poll(remove는 다 비워졌으면 에러, poll는 null 반환)
다 없앨때 clear
맨앞값 확인 element, peek(전자는 에러, 후자는 null)
[JAVA] Queue(큐) 사용법 (add vs offer / remove vs poll / element vs peek) :: 코딩 공부 일지 (tistory.com)

[JAVA] Queue(큐) 사용법 (add vs offer / remove vs poll / element vs peek)

 

package baekjoon;
import java.util.*;
import java.io.*;

public class b1240 {
	static int node[][];
	static int distance[][];
	static boolean visited[]; 
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n, m, row, col, cost, start, end;
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		node = new int[n+1][n+1];
		distance = new int[n+1][n+1];
		
		for(int i = 0 ; i < n-1 ; i++)
		{
			st = new StringTokenizer(br.readLine());
			row = Integer.parseInt(st.nextToken());
			col = Integer.parseInt(st.nextToken());
			cost = Integer.parseInt(st.nextToken());
			distance[row][col] = cost;
			distance[col][row] = cost;
			node[row][col] = 1;
			node[col][row] = 1;
		}
		
		for(int i = 0 ; i < m ; i++)
		{
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());			
			bfs(start, end, n);
		}	
	}
	public static void bfs(int start, int end, int n)
	{
		visited = new boolean[n+1];
		visited[start] = true;

		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		
		int res[] = new int[n+1];

		while(!queue.isEmpty())
		{
			int cur = queue.poll();
			
			for(int i = 1 ; i <= n ; i++)
			{
				if(node[cur][i] == 1 && !visited[i])
				{
					res[i] += distance[cur][i] + res[cur];
					if(i == end)
					{
						System.out.println(res[i]);
						return;
					}
					queue.offer(i);
					visited[i] = true;
				}
			}
			
		}
		
		
	}
}

구글링 해서 이해하고 쓰다가 잘 모르겠으면 다시 읽다가 쓰는 방식으로 했는데요..
저번 객체 중간이랑 내용 겹쳐서 이해는 할만했던 거 같습니다..
[백준] 노드 사이 거리 (1240) - Java, bfs — Log sey (tistory.com)

[백준] 노드 사이 거리 (1240) - Java, bfs

이 선생님 글 열심히 봤습니다
node[row][col] 이부분 귀찮아서 복붙해놓고 col row로 수정 안 해서
막판에 오류나길래 엥??하면서 한 30분 붙잡고 있었는데 이 실수였네요..
재밌네요

지금 상태

지금 상태2