[programmers] ๋คํธ์ํฌ - Java
์ปดํจํฐ์ ๊ฐ์์ ์ฐ๊ฒฐ ์ ๋ณด๋ฅผ ๋ฐํ์ผ๋ก ๋คํธ์ํฌ์ ๊ฐ์๋ฅผ ๋ฐํํ๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด, ์ฒ์์๋ ๋ ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ๋ ๋๋ง๋ค ๋คํธ์ํฌ ์๋ฅผ ๊ฐ์์ํค๋ ๋ฐฉ์์ ์ฌ์ฉํ์ผ๋, ์ด๋ ๊ฐ์ ์ฐ๊ฒฐ์ ๊ณ ๋ คํ์ง ์์ ์ ํํ์ง ์์๋ค. ์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ๊น์ด ์ฐ์ ํ์(DFS)๋ฅผ ์ ์ฉํ์ฌ, ๋ฐฉ๋ฌธํ์ง ์์ ์ปดํจํฐ๊ฐ ์์ ๊ฒฝ์ฐ DFS๋ฅผ ์คํํ๊ณ , ๋ฐฉ๋ฌธํ ์ปดํจํฐ๋ฅผ ํ์ํ๋ฉฐ, ํด๋น ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ปดํจํฐ๋ฅผ ์ํํ๋ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์๋ค.
Apr 08, 2024
๋คํธ์ํฌ
๋ฌธ์ ์ค๋ช
๋คํธ์ํฌ๋ ์ปดํจํฐ ์ํธ ๊ฐ์ ์ ๋ณด๋ฅผ ๊ตํํ ์ ์๋๋ก ์ฐ๊ฒฐ๋ ํํ๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ์ปดํจํฐ A์ ์ปดํจํฐ B๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด์๊ณ , ์ปดํจํฐ B์ ์ปดํจํฐ C๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ ๋ ์ปดํจํฐ A์ ์ปดํจํฐ C๋ ๊ฐ์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์ ๋ณด๋ฅผ ๊ตํํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ปดํจํฐ A, B, C๋ ๋ชจ๋ ๊ฐ์ ๋คํธ์ํฌ ์์ ์๋ค๊ณ ํ ์ ์์ต๋๋ค.
์ปดํจํฐ์ ๊ฐ์ n, ์ฐ๊ฒฐ์ ๋ํ ์ ๋ณด๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด computers๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋คํธ์ํฌ์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์์ค.
์ ํ์ฌํญ
- ์ปดํจํฐ์ ๊ฐ์ n์ 1 ์ด์ 200 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- ๊ฐ ์ปดํจํฐ๋ 0๋ถํฐ
n-1
์ธ ์ ์๋ก ํํํฉ๋๋ค.
- i๋ฒ ์ปดํจํฐ์ j๋ฒ ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด computers[i][j]๋ฅผ 1๋ก ํํํฉ๋๋ค.
- computer[i][i]๋ ํญ์ 1์ ๋๋ค.
์ ์ถ๋ ฅ ์
n | computers | return |
3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์์ #1
์๋์ ๊ฐ์ด 2๊ฐ์ ๋คํธ์ํฌ๊ฐ ์์ต๋๋ค.
์์ #2
์๋์ ๊ฐ์ด 1๊ฐ์ ๋คํธ์ํฌ๊ฐ ์์ต๋๋ค.
์ฒ์ ์์ฑํ ์ฝ๋
class Solution { public int solution(int n, int[][] computers) { int answer = n; for(int i=0; i<computers.length-1; i++){ for(int j=i+1; j<computers[i].length; j++){ if(computers[i][j]==1) answer--; if(answer==1) return answer; } } return answer; } }
์์ ํ ์ฝ๋
class Solution { public int solution(int n, int[][] computers) { boolean[] visited = new boolean[n]; int networks = 0; for (int i = 0; i < n; i++) { System.out.println(visited[i]); if (!visited[i]) { dfs(computers, visited, i); networks++; } } return networks; } private void dfs(int[][] computers, boolean[] visited, int node) { visited[node] = true; for (int neighbor = 0; neighbor < computers.length; neighbor++) { if (computers[node][neighbor] == 1 && !visited[neighbor]) { dfs(computers, visited, neighbor); } } } }
ํต์ฌ ํค์๋
- ์ฒ์ ์์ฑํ ์ฝ๋๋ ๋ ์ปดํจํฐ ๊ฐ์ ์ฐ๊ฒฐ์ด ๋ฐ๊ฒฌ๋ ๋๋ง๋ค ๋คํธ์ํฌ ๊ฐ์๋ฅผ ๊ฐ์์์ผ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ค๊ณ ํ๋ค.
- ๊ทธ๋ฌ๋ ์ด ๊ฒฝ์ฐ ๊ฐ์ ์ฐ๊ฒฐ์ ๊ณ ๋ คํ์ง ์๊ณ ์ง์ ์ฐ๊ฒฐ ์๋ง ๊ณ์ฐํ๋ฏ๋ก ๋คํธ์ํฌ ์๋ฅผ ์ ํํ๊ฒ ๊ณ์ฐํ์ง ๋ชปํ๋ค.
- ์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด DFS๋ฅผ ์ ์ฉํด์ ์ฝ๋๋ฅผ ์์ฑํ๋ค.
- DFS ์ํ ์ค์ ๋ฐฉ๋ฌธํ ์ปดํจํฐ๋ฅผ ์ถ์ ํ๋ ๋ฐ ์ฌ์ฉํ
boolean ๋ฐฐ์ด
์ ์ ์ธํด์, ๋ง์ฝ ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉดdfs()
๋ฅผ ์คํํ๋ค. dfs()
๋ฅผ ์คํํ๋ฉด ๋ฐฉ๋ฌธํ ์ปดํจํฐ๋ฅผ ํ์ํ๊ณ , ํด๋น ์ปดํจํฐ์ ๋ค๋ฅธ ์ปดํจํฐ์ ์ฐ๊ฒฐ ์ฌ๋ถ๋ฅผ ์ํํ๋ค.- ํด๋น ์ปดํจํฐ๊ฐ ๋ค๋ฅธ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋์ด ์๊ณ , ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ฅผ ๋ฐฉ๋ฌธํ์ง ์์์ ๊ฒฝ์ฐ
dfs()
๋ฉ์๋๋ฅผ ์ฌ๊ท ํธ์ถํ๋ค. - ํด๋น ์ปดํจํฐ์ ๋ฐฉ๋ฌธ์ด ์๋ฃ๋๋ฉด ๋คํธ์ํฌ ์๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ DFS๋ก ๋ฌธ์ ๋ฅผ ์ ๊ทผํ๋ ๋ฐฉ์์ ๋ํด ์ข ๋ ์๊ฐํด ๋ณผ ์ ์์๋ค.
Share article