[Programmers] 타겟 넘버

타겟 넘버

풀이

• 음이 아닌 정수들이 Numbers 배열로 주어지고, "순서를 바꾸지 않고" 적절히 더하거나 빼서 주어진 target 넘버와 같아지면 answer+1 해주면 되는 문제.

• dfs/bfs 문제로 분류 되어 있어서, numbers 배열을 2차원 배열로 나타내려고 했다.
  numbers = [[1,1,1,1,1],[-1,-1,-1,-1,-1]] 이런식으로,,,

• 이렇게 배열을 만들어 두고,"순서를 바꾸지 않고" 라는 문제의 조건이 있으니까, 아! 오른쪽, 대각선 위 오른쪽, 대각선 아래 오른쪽으로만 이동할 수 있겠구나 ! 하면서 dx = {0,1,-1}; dy={1,1,1} 로 설정해서 bfs를 돌렸다.

• 근데 아무생각 없이 bfs를 돌렸는데 계속 답이 안나오는거다. 생각해보니 visited 배열이 필요 없는 문제였다. 모든 경우의 수를 봐야 하니까 ...

• visited 배열 없애고, {0,0} 에서 시작하는 경우와 {0,1}에서 시작하는 경우 두개를 고려하기 위해 bfs(0,0), bfs(0,1) 로 함수를 실행시켜 맞혔다.

  😇 내 풀이 (bfs)

  import java.util.*;
  import java.io.*;
  class Solution {
      static int[][] map;
      static int size;
      static int[] dx = {0,1,-1};
      static int[] dy = {1,1,1};
      static int targetNum;
      static int answer;
      public int solution(int[] numbers, int target) {
          answer = 0;
          size = numbers.length;
          targetNum = target;
          map = new int[2][size];
          for(int i=0;i<size;i++){
              map[0][i] = numbers[i];
              map[1][i] = numbers[i]*(-1);
          }
          bfs(0,0);
          bfs(1,0);
          return answer;
      }
      private static boolean bfs(int i, int j){
          Queue<int[]> queue = new LinkedList<>();
          queue.add(new int[]{i,j,map[i][j]});
          while(!queue.isEmpty()){
              int[] now = queue.poll();
              int nowX = now[0];
              int nowY = now[1];
              int sum = now[2];
              if(nowY==size-1 && sum==targetNum){
                  answer++;
              }
              else{
                  for(int k=0;k<3;k++){
                      int nx = nowX+dx[k];
                      int ny = nowY+dy[k];
                      if(nx>=0 && nx<=1 && ny>=0 && ny<size){
                          queue.add(new int[]{nx,ny,map[nx][ny]+sum});
                      }
                  }
              }
          }
          return false;
      }
  }

• 다른 사람들 풀이를 참고해보니, dfs가 훨씬 간단하다고 함. 그리고 2차원 배열 굳이 필요하지 않은 문제였다 . ..

  dfs 풀이

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