프로그래머스 - 타겟 넘버 [자바]

• 문제 링크 : 타겟 넘버

코딩테스트 연습 - 타겟 넘버

 

정답

 

1. 재귀 : dfs함수가 int를 리턴하는 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        answer = dfs(numbers, 0, 0, target);

        return answer;
    }

    private int dfs(int[] numbers, int nodeNum, int sum, int target){
        if(nodeNum == numbers.length){
            if(sum == target){
                return 1;
            }else{
                return 0;
            }
        }else{
            return dfs(numbers, nodeNum + 1, sum - numbers[nodeNum], target)
                + dfs(numbers, nodeNum + 1, sum + numbers[nodeNum], target);
        }
    }
}

 

 

2. 재귀 : dfs함수가 void로 아무것도 리턴하지 않는 풀이

class Solution {
    private int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, 0, target, 0);
        
        return answer;
    }
    
    private void dfs(int[] numbers,int depth, int target, int sum){
        if(numbers.length == depth){
            if(sum == target){
                answer++;
            }
            return;
        }
        
        dfs(numbers, depth + 1, target, sum - numbers[depth]);
        dfs(numbers, depth + 1, target, sum + numbers[depth]);
        
    }
}

 

3. Stack 풀이

import java.util.*;

class Solution {
    
    private class Val{
        int depth, sum;
        
        Val(int depth, int sum){
            this.depth = depth;
            this.sum = sum;
        }
    }
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        Stack<Val> stk = new Stack<>();
        
        stk.push(new Val(0, 0));
        
        while(!stk.isEmpty()){
            
            Val val = stk.pop();
            
            if(val.depth < numbers.length){
                stk.push(new Val(val.depth + 1, val.sum + numbers[val.depth]));
                stk.push(new Val(val.depth + 1, val.sum - numbers[val.depth]));
            }else{
                if(val.sum == target){
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

 

분석

깊이 우선 탐색(Depth-First Search, DFS)이나 너비 우선 탐색(Breadth-First Search, BFS)으로 풀 수 있는 문제이다.

 

BFS 보다 DFS가 간편하여 DFS로 풀이 하였다.

 

return 에서 +를 기준으로 sum에서 - 와 +를 해주어 -1, +1을 할 수 있도록 하였다.

 

if문에서 sum과 target이 같은 경우만 1을 리턴하여 target 값이 몇 개가 있는지 마지막 결과로 받을 수 있다.

 

 

함수 형식 : dfs(숫자배열, 차수, 총합, 목표값) return dfs() + dfs()

 

참조한 코드

 

• C

 

#include <stdio.h>

#define N 7

int g[N][N]=
{
    {0,1,0,0,0,1,1},
    {1,0,1,1,0,0,0},
    {0,1,0,0,1,0,0}, 
    {0,1,0,0,0,0,0},
    {0,0,1,0,0,0,0},
    {1,0,0,0,0,0,1},
    {1,0,0,0,0,1,0}
};
int visited[N];

void dfs(int here) {

    //here이 이미 방문된 정점 return
    if (visited[here]) return;

    printf("정점 %d를 방문\n", here);

    visited[here] = 1;  //here 정점은 방문

    for (int next = 0; next < N; next++) 
        //그래프가 이어져있으면서, 아직 다음 정점이 방문되지 않았으면 dfs 수행
        if (g[here][next] == 1 && !visited[next]) dfs(next);
}

int main() {
    dfs(0);
}

 

• Java

 

/*
    0 : 연결 안됨
    1 : 연결됨

    아래 단순 7개의 정점 있는 그래프를 표현 한 것
    노드 1 - 노드 2 - 노드 6 - 노드 7
    노드 2 - 노드 1 - 노드 3 - 노드 4
    노드 3 - 노드 2 - 노드 5
    노드 4 - 노드 2
    노드 5 - 노드 3
    노드 6 - 노드 1 - 노드 7
    노드 7 - 노드 1 - 노드 6

    * 그림 *
    노드 1 --- 노드 2 --- 노드 3 --- 노드 5
      ㅣ         ㅣ
      ㅣ         ㅣ------ 노드 4
      ㅣ
      ㅣ------ 노드 6
      ㅣ         ㅣ
      ㅣ------ 노드 7

*/
int[][] graph = 
{
    {0,1,0,0,0,1,1},
    {1,0,1,1,0,0,0},
    {0,1,0,0,1,0,0}, 
    {0,1,0,0,0,0,0},
    {0,0,1,0,0,0,0},
    {1,0,0,0,0,0,1},
    {1,0,0,0,0,1,0}
};
int[] visited = new int[graph.length];
private void dfs(int nodeNum){

    /*방문된 정점이라면 뒤로 가기*/
    if(visited[nodeNum]){
        return;
    }

    /*현재 정점은 방문*/
    visited[nodeNum] = 1;

    for(int next = 0; next < graph.length; next++){
        /*그래프가 이어져 있으며 아직 다음 정점을 방문하지 않았으면*/
        if(graph[nodeNum][next] == 1 && !visited[nodeNum]){
            /*다음 정점에서 dfs*/
            dfs(next);
        }
    }
}

dfs(0);