https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
깊이/너비 우선 탐색(DFS/BFS)
타겟넘버
class Solution {
static int answer = 0;
public int solution(int[] numbers, int target) {
DFS(numbers, target, 0, 0);
return answer;
}
public static void DFS(int[] numbers, int target, int sum, int dep){
int initial_depth = numbers.length;
if(dep == initial_depth){
if(sum == target) answer++;
}
else{
DFS(numbers, target, sum + numbers[dep], dep+1);
DFS(numbers, target, sum - numbers[dep], dep+1);
}
}
}
네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분명히 맞게 푼 것 같은데 계속 에러가 떠서 당황했다
에러의 이유는 인접 리스트 A를 초기화해주지 않아서였다. 난 바보인가
import java.util.ArrayList;
/*
직접 네트워크 갯수: edge(간선) 갯수
간선이 연결되어 있으면 하나의 네트워크임.
computer[i][j] = 1이면 인접 노드 ArrayList에 i와 j를 추가
그리고 간선 갯수 카운팅
*/
class Solution {
static ArrayList<Integer>[] A;
static boolean visited[];
public int solution(int n, int[][] computers) {
int answer = 0;
A = new ArrayList[n];
visited = new boolean[n];
//인접 리스트 초기화
for(int i = 0; i < n; i++) {
A[i] = new ArrayList<Integer>();
}
/*computers[i][j]가 1이고 i==j가 아닐 때
i와 j는 인접하여 있으므로 인접 리스트에 추가해 */
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(computers[i][j] == 1 && i != j){
A[j].add(i);
A[i].add(j);
}
}
}
//노드 갯수만큼 돌려서 edge 갯수 구하면 될듯?
for(int i = 0; i < n; i++){
if(!visited[i]){
answer++;
DFS(i);
}
}
return answer;
}
static void DFS(int node){
if(visited[node]) return; //종료조건
visited[node] = true; //방문했으므로 true로 바꿔
//인접리스트에 있는 요소들을 쭉 반복하면서
for(int a: A[node]){
//방문하지 않은 A[node]이면 DFS 재귀 돌려
if(visited[a] == false)
DFS(a);
}
}
}
'Algorithms > programmers' 카테고리의 다른 글
[이분탐색] 징검다리 건너기 (0) | 2024.01.23 |
---|---|
[이분탐색] 프로그래머스 입국심사 (0) | 2024.01.11 |
[Greedy] 프로그래머스 체육복, 큰 수 만들기, 구명보트, 단속카메라 (1) | 2023.12.28 |
[Dynamic Programming] 프로그래머스 정수삼각형 (0) | 2023.12.26 |
[완전탐색] 프로그래머스 최소직사각형 (0) | 2023.12.01 |