[BFS] 네트워크

[BFS] 네트워크

문제 바로가기

아주 간단한 BFS 문제입니다.

프로그래머스 구경하다가.. 문제가 너무 쉬워보일길래 한 번 풀어보았습니다.

IDE 안쓰고 코드짜는 것도 나름 재밌네요.

import java.util.*; class Solution { public boolean[] visited; public List[] graph; public int solution(int n, int[][] computers) { int answer = 0; visited = new boolean[n]; Arrays.fill(visited, false); graph = new List[n]; for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (computers[i][j] != 1) continue; graph[i].add(j); graph[j].add(i); } } for (int i = 0; i < n; i++) { System.out.println(graph[i].toString()); } for (int i = 0; i < n; i++) { if (!visited[i]) { answer++; bfs(i); } } return answer; } public void bfs(int start) { Queue q = new LinkedList<>(); q.offer(start); visited[start] = true; while(!q.isEmpty()) { int cur = q.poll(); for (int i = 0; i < graph[cur].size(); i++) { int next = graph[cur].get(i); if (visited[next]) continue; visited[next] = true; q.offer(next); } } } }

입사하기 전에는 for 나 if 뒤에 띄어쓰기를 절대 안했는데 이제 안하면 찝찝합니다.

암튼 이 문제는 인풋이 더럽게도 2차원 배열로 주어집니다. 것도 그래프가요. 따라서 저는 List 배열로 예쁜 그래프를 만들어놓고 문제를 풀었습니다.

걍 뭐... 겁나게 단순합니다. 총 몇 개의 네트워크가 있냐 == BFS 타고 들어갈 수 있는게 몇 개냐 라고 볼 수 있습니다.

고로 visited[] 체크를 하면서 방문한 적이 없는 노드(컴퓨터)가 있다면 걔는 이전 네트워크들과는 별개의 네트워크를 형성하니깐 answer++ 되는 것이지요.

나중에 여유가 생기고 하고 싶은 맘이 생기면 릿코드도 시작해야겠습니다.

하지만 역시 노는게 제일 좋아~~

그럼 20000

from http://yoon1fe.tistory.com/242 by ccl(A) rewrite - 2021-11-09 01:00:37