๋ฌธ์ ์ ๊ทผ
https://school.programmers.co.kr/learn/courses/30/lessons/92343
ํ๋ก๊ทธ๋๋จธ์ค
SW๊ฐ๋ฐ์๋ฅผ ์ํ ํ๊ฐ, ๊ต์ก์ Total Solution์ ์ ๊ณตํ๋ ๊ฐ๋ฐ์ ์ฑ์ฅ์ ์ํ ๋ฒ ์ด์ค์บ ํ
programmers.co.kr
์ฒ์์๋ ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๋ ์๊ฐ์ ์ต๋ 17๊ฐ์ ๋ ธ๋์ด๋ฏ๋ก ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ์ ๋ถ ๋ฐ์ ธ๋ณด๋ฉด ๋ ๊ฒ ๊ฐ์์
ํ์ง๋ง, ์ฌ๊ท ๊ตฌํ ๊ณผ์ ์์ ์๊พธ ๋ฌดํ๋ฃจํ๊ฐ ๋ฐ์ํด์ ํ๋ค์๋ ๋ฌธ์
๋ฌธ์ ํ์ด
์ด ๋ฌธ์ ์ ํต์ฌ ํฌ์ธํธ๋ ํ์ฌ ๋ ธ๋ ๊ธฐ๋ฐ์ด ์๋๋ผ ํ์ฌ ์ํ(์, ๋๋, ๋ค์ ๋ฐฉ๋ฌธ ๊ฐ๋ฅ ๋ ธ๋ ๋ชฉ๋ก)์ผ๋ก ํ์์ ์งํํด์ผ๋๋ค๋ ๊ฒ์
=> ์ฆ, ์ง๊ธ๊น์ง ๋ฐฉ๋ฌธํ ๋ชจ๋ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ชจ๋ ์์ ๋ ธ๋๋ค ์ค์์ ํ๋๋ฅผ ๊ณจ๋ผ ๋ค์์ผ๋ก ๋ฐฉ๋ฌธํด์ผ ๋ฌดํ ๋ฃจํ์์ด ๋ฌธ์ ๋ฅผ ์ ๋๋ก ํ ์ ์์
์ฐ์ , ์์ ์ต๋๊ฐ์ ์ ์ฅํ๋ max์ ๊ฐ ๋ ธ๋๋ณ ์๊ณผ ๋๋ ์ฌ๋ถ๋ฅผ ๋ํ๋ด๋ info๋ฅผ ์ ์ญ ๋ณ์ infoArr๋ก ์ ์ธํด์คฌ์
๊ทธ๋ฆฌ๊ณ ๊ฐ ๋ ธ๋๋ณ๋ก ๋ค์์ ์ด๋ํ ์ ์๋ (์ฐ๊ฒฐ๋) ์์ ๋ ธ๋ ๋ฒํธ๋ฅผ ์ ์ฅํด๋๊ธฐ ์ํด List<List<Integer>>๋ฅผ ์ ์ธํด์คฌ์
=> ์ด ๋ ์ธ๋ฑ์ค ์๋ฌ๋ฅผ ๋ฐฉ์งํ๊ธฐ์ํด ๊ฐ ๋ ธ๋๋ณ๋ก ArrayList๋ฅผ ๋จผ์ ์ด๊ธฐํํด์ฃผ๊ณ ๊ฐ ๋ ธ๋๋ณ๋ก ์์ ๋ ธ๋ ๋ฒํธ๋ฅผ ์ ์ฅํด์ผํจ
์ด๋ ๊ฒ List๊น์ง ์์ฑํ๋ค๋ฉด ์ฌ๊ท๋ฅผ ํตํด ์ ๋ต์ ๊ตฌํ๋ฉด๋๋๋ฐ ํ์ฌ ์ํ์์ ์์ ๊ฐ์, ๋๋์ ๊ฐ์, ๋ค์ ์ด๋ํ ์ ์๋ ๋ ธ๋๋ค์ List๋ฅผ ๋งค๊ฐ๋ณ์๋ก ๋ฐ๋ dfs ํจ์๋ฅผ ์ ์ธํด์คฌ์
=> ์ฒซ ๋ฃจํธ ๋ ธ๋๋ ๋ฌด์กฐ๊ฑด 0๋ฒ์ด๊ณ ์ 1๋ง๋ฆฌ๊ฐ ์กด์ฌํ๋ฏ๋ก dfs๋ฅผ ์ฒ์ ํธ์ถํ ๋๋ ์ 1๋ง๋ฆฌ, ๋๋ 0๋ง๋ฆฌ, tree.get(0)์ ํตํด 0๋ฒ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ์์๋ค์ ๋๊ฒจ์ค์ผํจ
dfsํจ์ ๋ด๋ถ์์๋ Math.max ํจ์๋ฅผ ํตํด ํ์ฌ ์ํ์์ ์์ ๊ฐ์๊ฐ max์ ์ ์ฅ๋ ์ต๋๊ฐ๋ณด๋ค ๋ง๋ค๋ฉด max๋ฅผ ํ์ฌ ์์ ๊ฐ์๋ก ๊ฐฑ์ ์์ผ์ค
=> ์๋ํ๋ฉด ๋ฌด์กฐ๊ฑด ํธ๋ฆฌ ์ ์ฒด๋ฅผ ํ์ํ ํ์ ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋๊ฒ ์๋๊ธฐ ๋๋ฌธ์ ์์ด ์ต๋๊ฐ ๋๋ ์๊ฐ์ด ํ์ ์ค๊ฐ์ ์์ผ๋ฉด ํด๋น ๋
ธ๋์์ ๋ฉ์ถฐ์ค์ ํํํ๊ธฐ ์ํด์
์ดํ ๋งค๊ฐ๋ณ์๋ก ์ ๋ฌ๋ฐ์ ํ์ฌ ์ํ์์ ์ด๋๊ฐ๋ฅํ ๋ ธ๋๋ค๋ก dfsํจ์๋ฅผ ์ ๊ฐํ๋๋ฐ ๋ค์ ์ด๋ํ ๋ ธ๋์ infoArr ์ ๋ณด๋ฅผ ํตํด 0์ด๋ฉด ์์ ๊ฐ์๋ฅผ, 1์ด๋ฉด ๋๋์ ๊ฐ์๋ฅผ ๋๋ ค์ฃผ๊ณ ๋๋๊ฐ ์์ ๊ฐ์์ ๋์ผํ๊ฑฐ๋ ์ปค์ง๋ฉด ๊ทธ ๋ค์ ํ์์ ์๋ฏธ๊ฐ ์์ด์ง๋ฏ๋ก continue์ฒ๋ฆฌํด์ค
=> ๋๋๊ฐ ์ก์๋จน์ผ๋ฉด ๊ทธ ๋ค์ ์ด๋ค ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํด๋ ๋ฌด์กฐ๊ฑด ๋๋์ ์์ ๊ฐ์๊ฐ ๊ฐ์์ง๊ฑฐ๋ ๋๋ ๊ฐ์๊ฐ ๋์ด๋๋ฏ๋ก ์ต๋์ ์ ๊ฐ์๊ฐ ๋์ฌ ์ ์์
๋ง์ฝ ๋ค์ ๋ ธ๋๋ก ์ด๋์ด ๊ฐ๋ฅํ๋ค๋ฉด (์์ด ๋๋๋ณด๋ค ๋ง๋ค๋ฉด) ๋ค์ ๋ฐฉ๋ฌธํ ๋ ธ๋๋ ์์ผ๋ก ๋ฐฉ๋ฌธํ ๋ ธ๋์ List์์ removeํด์ฃผ๊ณ ๋ค์ ๋ฐฉ๋ฌธํ ๋ ธ๋์์ ๋ ๋ค์์ผ๋ก ๋ฐฉ๋ฌธํ ์ ์๋ ์์๋ค์ ๊ฒฝ์ฐ๋ฅผ List์ ์ถ๊ฐํด์ค
=> ์ด์ ์ด๋ ๊ฒ ๋ค์ ๋ ธ๋๋ก ์ด๋ํ ์ํ๋ก ๊ฐฑ์ ๋ ์์ ๊ฐ์, ๋๋์ ๊ฐ์, ์ด๋ ๊ฐ๋ฅํ ๋ ธ๋ List๋ฅผ ๋ด์์ dfs๋ฅผ ์ฌ๊ท ํธ์ถ์์ผ์ฃผ๋ฉด๋จ
dfsํจ์๊ฐ ์ข ๋ฃ๋๋ฉด max์๋ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๋ฉฐ ์์ ๊ฐ์๊ฐ ์ต๋์๋ ์์ ์ ์์ ๊ฐ์๊ฐ ๋ด๊ฒจ์ ธ์์ผ๋ฏ๋ก ์ด๋ฅผ returnํ๋ฉด ๋๋จ
์ ์ฒด ์ฝ๋
import java.util.*;
class Solution {
int max = -1;
int[] infoArr;
List<List<Integer>> tree = new ArrayList<>();
void dfs(int sheep, int wolf, List<Integer> nextNodes) {
// ํ์ฌ ์์ ๊ฐ์๊ฐ max๋ณด๋ค ๋ง๋ค๋ฉด ๊ฐฑ์
max = Math.max(max, sheep);
// ๋ค์์ ์ด๋ ๊ฐ๋ฅํ (์์)๋
ธ๋๋ค๋ก ์ ๊ฐ
for(int i = 0; i < nextNodes.size(); i++) {
int nextNode = nextNodes.get(i);
int newSheep = sheep;
int newWolf = wolf;
// ๋ค์ ๋
ธ๋๊ฐ 0์ด๋ฉด ์
if(infoArr[nextNode] == 0) {
newSheep++;
} else { // 1์ด๋ฉด ๋๋
newWolf++;
}
// wolf๊ฐ ์ก์๋จน์ผ๋ฉด ๊ทธ ๋ค์ ํ์์ ์๋ฏธ X
if(newWolf >= newSheep) continue;
List<Integer> newNextNodes = new ArrayList<>(nextNodes);
// ๋ค์ ๋ฐฉ๋ฌธํ ๋
ธ๋(ํ์ฌ i๊ฐ ๊ฐ๋ฆฌํค๋ ๋
ธ๋)๋ ์์ผ๋ก ๋ฐฉ๋ฌธํ ๋
ธ๋์์ ์ ๊ฑฐํด์ค
newNextNodes.remove(i);
// ๋ค์ ๋ฐฉ๋ฌธํ ๋
ธ๋(ํ์ฌ i๊ฐ ๊ฐ๋ฆฌํค๋ ๋
ธ๋)์์ ๋ฐฉ๋ฌธํ ์์๋ค์ ์์ผ๋ก ๋ฐฉ๋ฌธํ ๋
ธ๋์ ์ถ๊ฐํด์ค
newNextNodes.addAll(tree.get(nextNode));
dfs(newSheep, newWolf, newNextNodes);
}
}
public int solution(int[] info, int[][] edges) {
infoArr = info;
// ๊ฐ node๋ณ๋ก ArrayList ์ด๊ธฐํ
for(int i = 0; i < info.length; i++) {
tree.add(new ArrayList<>());
}
// ๊ฐ node๋ณ๋ก ๊ฐ ์ ์๋ ์์ node ๋ฒํธ๋ฅผ ์ ์ฅํด๋
for(int[] edge : edges) {
tree.get(edge[0]).add(edge[1]);
}
// ๋ฃจํธ ๋
ธ๋(์ 1๋ง๋ฆฌ) ๋ถํฐ ์์
dfs(1, 0, tree.get(0));
return max;
}
}'๐ฅ Algorithm > ์์ ํ์' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [ํ๋ก๊ทธ๋๋จธ์ค] ์ฒด์ก๋ํ (JAVA ํ์ด) (0) | 2025.10.31 |
|---|---|
| [ํ๋ก๊ทธ๋๋จธ์ค] ์ฌ๋ผ์ง๋ ๋ฐํ (JAVA ํ์ด) (0) | 2025.10.28 |
| [ํ๋ก๊ทธ๋๋จธ์ค] ์๊ถ๋ํ (JAVA ํ์ด) (0) | 2025.10.25 |