프로그래머스 - 가장 먼 노드(java)

🐴 문제

📃프로그래머스 - 가장 먼 노드

그래프 카테고리의 level3문제다.

처음 풀어보는 그래프 문제라 처음에 헤맸다. 그래도 이 문제를 풀면서 언제 bfs를 써야하는지 감이 좀 잡혔다.

bfs를 공부할겸 인접리스트로 푸는 방법, 인접행렬로 푸는 방법 두 가지로 풀어봤다.

🐴 bfs

bfs 문제를 푸는 방법은 인접리스트를 이용하는 방법, 인접행렬을 이용하는 방법 두가지가 있다.

푸는 방법은

• 인접리스트 : 존재하는 간선에 대해서만 탐색을 한다.
• 인접행렬 : 모든 정점에 대해 탐색

시간복잡도로 보면
G: 그래프, V: 정점, E: 간선

• 인접리스트 : O(V+E)
• 인접행렬 : O(V^2)

🐴 로직 - 인접리스트

*테스트케이스

기본 테스트케이스를 조금 변형한 아래의 테스트케이스로 로직을 설명한다.
6, [[3, 6], [1, 3], [1, 2], [2, 4], [5, 2]]

1. 인접 리스트 만들기

간선의 방향이 양방향 이므로 인접 리스트 양쪽 노드에 모두 추가

2. bfs로 탐색

시작 노드가 1(0)로 정해져있다.
bfs메서드에 탐색해야할 노드를 큐로 넘겨준다.

🐴 코드 - 인접리스트

public int solution(int n, int[][] edge) {
	/* 인접 리스트에 데이터 추가*/
	//인접리스트 생성
	List<List<Integer>> adList = new ArrayList<>();
	//노드수만큼 초기화
	for (int i = 0; i < n; i++) {
		adList.add(new ArrayList<Integer>());
	}
	//데이터 추가
	for (int[] e : edge) {
		adList.get(e[0] - 1).add(e[1] - 1);
		adList.get(e[1] - 1).add(e[0] - 1);
	}
	
	Queue<Integer> q = new LinkedList<>();
	q.offer(0);
	
	boolean[] check = new boolean[n];
	check[0] = true;

	return bfs(adList, q, check);
}


public int bfs(List<List<Integer>> adList, Queue<Integer> q, boolean[] check) {
	int answer = q.size();		
	Queue<Integer> q2 = new LinkedList<>();
	
	/* 1. 다음 depth에 해당하는 노드를 확인하고 큐에 담는다.*/
	while(!q.isEmpty()) {
		for (int i : adList.get(q.poll())) {
			if (!check[i]) {
				check[i] = true;
				q2.offer(i);
			}
		}
	}
	/* 2. 다음 depth가 없다면 return */
	if(q2.size()==0) return answer;
	/* 2. 있다면 bfs */
	answer = bfs(adList, q2, check);

	return answer;
}

🐴 로직 - 인접행렬

1. 인접행렬 만들기

boolean타입의 2차원 배열로 행렬을 사용했다.

🐴 코드 - 인접행렬

public int solution(int n, int[][] edge) {
	/*1. 인접행렬에 담기  */
	boolean[][] arr = new boolean[n+1][n+1];
	
	for(int[] e : edge) {
		arr[e[0]][e[1]] = true;
		arr[e[1]][e[0]] = true;
	}
	
	Queue<Integer> q = new LinkedList<Integer>();
	q.offer(1);
	boolean[] check = new boolean[n+1];
	check[1] = true;
	/* 2. bfs*/
	return bfs(arr, q, check);
}


public int bfs(boolean[][] arr, Queue<Integer> q, boolean[] check) {
	int size = q.size();	//현제 Depth의 노드 수 
	
	/* 다음 탐색해야할 노드들 큐에 담기  */
	Queue<Integer> q2 = new LinkedList<Integer>();
	while(!q.isEmpty()) {
		for(int i = 1; i < check.length ; i++) {
			if(arr[q.peek()][i] && !check[i]) {
				check[i] = true;
				q2.offer(i);
			}
		}
		q.poll();
	}
	/* 다음 탐색해야할 노드가 없다면(지금이 마지막 depth라면) size 리턴*/
	if(q2.isEmpty()) {
		return size;
	}
	
	return bfs(arr, q2, check);
}