자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 송아지 찾기 1 (BFS : Breadth-First Search)

 

https://hyejin.tistory.com/1259

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진트리 순회 (BFS : Breadth-Fir

-> 이전 문제 풀이 

 

 

8. 송아지 찾기 1 (BFS : Breadth-First Search)

설명

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.

 

출력

점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.

 

예시 입력 1 

5 14

 

예시 출력 1

3

 

 

문제 풀이 1

public class FindTheCalf
{
   static int[] ch; // 갔던 좌표인지 확인하기 위한 배열
   static int[] jump = { -1, 1, 5 }; // jump -1, 1, 5
   
   public int  BFS(int s, int e) // L 은 현재 위치
   {
      int answer = 0;
      Queue<Integer> Q = new LinkedList<>();
      int L = 1; // 점프 횟수
      Q.offer(s);
      
      while (!Q.isEmpty())
      {
         int len = Q.size();
         for (int j = 0; j < len; j++)
         {
            Integer cur = Q.poll();
            for (int i = 0; i < jump.length; i++)
            {
               if (cur + jump[i] > 0)
               {
                  if(cur + jump[i] == e)
                  {
                     return L;
                  }
                  else if (ch[cur + jump[i]] == 0)
                  {
                     Q.offer(cur + jump[i]);
                     ch[cur + jump[i]] = 1;
                  }
               }
            }
         }
         L++; // 한 번 더 점프
      }
      
      return L;
   }
   
   public static void main(String[] args)
   {
      FindTheCalf findTheCalf = new FindTheCalf();
      Scanner scanner = new Scanner(System.in);
      int s = scanner.nextInt(); // 현수의 위치
      int e = scanner.nextInt(); // 송아지의 위치
      ch = new int[10001];
      
      int result = findTheCalf.BFS(s, e);
      System.out.println(result);
   }
}

👩‍💻 : 섹션 7에서 드디어 내가 직접 풀어서 정답을 구했다........⭐

 

https://hyejin.tistory.com/1258

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 부분집합 구하기 (DFS)

https://hyejin.tistory.com/1259

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진트리 순회 (BFS : Breadth-Fir

부분 집합 풀이랑 이진트리 순회 BFS 풀이에서 힌트를 얻어 문제를 풀었다. 

 

점프 횟수가 이진트리 순회 BFS 풀이의 레벨이라고 할 수 있다. 

 

 

 

 

이렇게 그림처럼 한 노드에서 -1, 1, 5 이렇게 점프해서 갈 수 있다. 

그리고 굳이 방문했던 노드는 또 다시 방문하지 않도록 하기 위해서 부분 집합때처럼 배열 ch를 만들고, 크기는 좌표가 10000까지라고 했으니 10000+1 로 초기화해준다. 그리고 방문했던 노드면 1, 아니면 0 으로 구분해준다. 

 

1️⃣

static int[] ch; // 갔던 좌표인지 확인하기 위한 배열
static int[] jump = { -1, 1, 5 }; // jump -1, 1, 5

 

따라서 이번 문제에서도 ch 배열에 방문한 노드는 1 아니면 0 으로 설정을 해줄 것이고, 

jump 라는 배열에 -1, 1, 5 점프할 수 있는 거리를 담아줬다.

 

 

2️⃣

int answer = 0;
Queue<Integer> Q = new LinkedList<>();
int L = 1; // 점프 횟수
Q.offer(s);

그리고 이번에도 Queue를 사용해서 레벨에 따른 원소를 담아줄 것이다. 

그리고 L은 1로 초기화해뒀는데 0으로 해도되고 상관 없다. 

근데 나는 그냥 현수의 위치가 송아지 위치와 같지는 않을 것이기 때문에 한번은 점프를 할것이라고 생각해서 1로 해줬다. 

그리고 문제보니까 답은 반드시 1 이상이며 반드시 답이 존재한다고 했기 때문에 L을 1로 줘도 된다. 

 

그리고 현수의 위치인 s를 root 노드로 먼저 Q에 offer 해준다. 

(이제 보니까 answer 변수는 필요 없음) 

 

 

 

3️⃣

while (!Q.isEmpty())
{
   int len = Q.size();
   for (int j = 0; j < len; j++)
   {
      Integer cur = Q.poll();
      for (int i = 0; i < jump.length; i++)
      {
         if (cur + jump[i] > 0)
         {
            if(cur + jump[i] == e)
            {
               return L;
            }
            else if (ch[cur + jump[i]] == 0)
            {
               Q.offer(cur + jump[i]);
               ch[cur + jump[i]] = 1;
            }
         }
      }
   }
   L++; // 한 번 더 점프
}

그리고 이제 while 문을 Q가 비어있지 않을 때 까지 돌면서 송아지의 위치를 찾아 나서면 된다. 

 

먼저 Q의 size를 len 변수로 선언해서 for문을 Q의 개수만큼 돌리면서 Q에서 poll한 cur 좌표에  -1, 1, 5 를 각각 더해 자식 노드를 만들어준다. 

그리고 이 자식 노드(좌표)는 1부터 시작이므로 cur + jump[i]가 0보다 커야 하고, 만약 이게 e와 같으면 바로 L를 리턴해주면 되고, e 송아지 위치와는 다른데 ch[cur + jump[i]] 가 0이라면 아직 방문하지 않은 노드(좌표)이므로 Q에 offer 해주고, 배열의 값을 1로 변경해준다. (그럼 다음엔 Q에 offer 하지 않을 수 있다.  굳이 방문했을 때 아니었던 노드를 또 Q에 offer 할 필요는 없다. 시간 복잡도만 늘어난다!) 

 

Q의 size만큼 반복문을 모두 돌고 나면 해당 레벨의 노드 (좌표)는 모두 한번 씩 돌았다는 것을 의미하므로 이제 다음 레벨로 넘어가야 한다. (한번 더 점프) 

 

이런식으로 해주면 최소 점프 횟수를 구할 수 있다. 

 

 

문제 풀이 2

public class FindTheCalf2
{
   int[] dis = { 1, -1, 5 };
   int[] ch; // 한번 방문한 것은 Q에 넣지 않기 위해서
   
   Queue<Integer> Q = new LinkedList<>();
   
   public int BFS(int s, int e)
   {
      ch = new int[10001];
      ch[s] = 1;
      Q.offer(s);
      int L = 0; // root node level
      
      while (!Q.isEmpty())
      {
         int len = Q.size(); // level에 있는 원소의 개수
         
         for (int i = 0; i < len; i++)
         {
            int x = Q.poll();
            for (int j = 0; j < dis.length; j++)
            {
               int nx = x + dis[j]; // 자식 노드
               if (nx == e) return L + 1; // 현재 L은 부모 노드의 레벨이므로 nx의 레벨로 해주기 위해 +1 를 해준다.
               if (nx >= 1 && nx <= 10000 && ch[nx] == 0) { // 방문 x
                  ch[nx] = 1;
                  Q.offer(nx);
               }
            }
         }
         L++;
      }
      
      return L;
   }
   
   public static void main(String[] args)
   {
      FindTheCalf2 findTheCalf2 = new FindTheCalf2();
      Scanner scanner = new Scanner(System.in);
      int s = scanner.nextInt(); // 현수의 위치
      int e = scanner.nextInt(); // 송아지의 위치
      
      int result = findTheCalf2.BFS(s, e);
      System.out.println(result);
   }
}

 

👾 : 문제 풀이2는 강사님 문제 풀이이다. 

 

int[] dis = { 1, -1, 5 };
int[] ch; // 한번 방문한 것은 Q에 넣지 않기 위해서

Queue<Integer> Q = new LinkedList<>();

강사님도 나와 같이 dis 배열에 -1, 1, 5 점프 할 수 있는 거리를 담아뒀고, 한번 방문한 것은 Q에 offer 하지 않기 위해서 ch 배열을 선언해줬다. 

 

public int BFS(int s, int e)
{
   ch = new int[10001];
   ch[s] = 1;
   Q.offer(s);
   int L = 0; // root node level
   
   while (!Q.isEmpty())
   {
      int len = Q.size(); // level에 있는 원소의 개수
      
      for (int i = 0; i < len; i++)
      {
         int x = Q.poll();
         for (int j = 0; j < dis.length; j++)
         {
            int nx = x + dis[j]; // 자식 노드
            if (nx == e) return L + 1; // 현재 L은 부모 노드의 레벨이므로 nx의 레벨로 해주기 위해 +1 를 해준다.
            if (nx >= 1 && nx <= 10000 && ch[nx] == 0) { // 방문 x
               ch[nx] = 1;
               Q.offer(nx);
            }
         }
      }
      L++;
   }
   
   return L;
}

확실히 강사님 코드가 더 깔끔하구나... 내 코드도 리팩토링이 필요할 듯... 중복코드가 꽤 많다. 

 

ch = new int[10001];
ch[s] = 1;
Q.offer(s);
int L = 0; // root node level

먼저 ch는 좌표가 10000까지 가능하다고 하니까 10000에 인덱스 0은 안쓸거니까 + 1 를 해서 10001 로 크기를 초기화해준다. 

 

그리고 ch[s]는 현수의 위치이므로 현수의 위치를 1로 선언해주고, 그 다음 Q에 현수의 위치 s를 먼저 offer 해준다. 

그렇게 해서 현수의 위치를 루트 노드로 설정해서 이제 거기서부터 자식 노드를 만들어가며 밑으로 쭉쭉 내려갈 것이다. 

 

그리고 강사님은 L을 root node의 레벨인 0으로 설정해줬다. 

 

while (!Q.isEmpty())
{
   int len = Q.size(); // level에 있는 원소의 개수
   
   for (int i = 0; i < len; i++)
   {
      int x = Q.poll();
      for (int j = 0; j < dis.length; j++)
      {
         int nx = x + dis[j]; // 자식 노드
         if (nx == e) return L + 1; // 현재 L은 부모 노드의 레벨이므로 nx의 레벨로 해주기 위해 +1 를 해준다.
         if (nx >= 1 && nx <= 10000 && ch[nx] == 0) { // 방문 x
            ch[nx] = 1;
            Q.offer(nx);
         }
      }
   }
   L++;
}

이제 while문을 Q가 비어있지 않을 때까지 반복해서 실행해주면 되는데

먼저 Q의 size를 구하고 이 크기만큼 for문을 돌린다. (해당 레벨에 들어있는 노드를 꺼낸다.) 

 

먼저 Q에서 하나를 poll 해서 이를 x라고 한다. 

그리고 dis 크기만큼 for문을 돌면서 x에 -1, 1, 5 값을 더해주는데 (이게 자식 노드가 된다.)

 

이 자식 노드가 만약 송아지의 위치다! 하면 현재 L은 부모 노드의 레벨에 해당하므로 리턴할 때는 자식 노드의 레벨로 해주기 위해 return L + 1 를 해주고 끝난다. 

 

자식 노드는 좌표가 1부터 10000사이 이므로 이 범위 안에 해당해야하고 (음수 안됨), 그리고 자식 노드 인덱스의 ch 배열에서 방문하지 않은 ch[nx] == 0 이라면 ch[nx] 을 1로 설정해주고, Q에 nx 값을 offer 해준다. (다음 레벨의 노드로 정해줌) 

 

이렇게 반복하면서 쭉쭉 내려가면 된다.