[BFS]송아지 찾기1

김우진·2022년 4월 14일
0

알고리즘 문제

목록 보기
6/21
post-thumbnail

송아지 찾기 1

설명

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

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

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

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

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

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

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

예시 입력
5 14

예시 출력
3

내가 처음에 짠 코드

  • Node를 만들어 현재 위치, 이동한 횟수등을 기억하고 그 노드에서 +1,-1,+5 이동한 경우를 queue에 넣어서 비교하도록 생각
  • 중복된 Node가 많으므로 이를 제거하기위해 check라는 List를 생각했지만, List는 primary type만 가능하여 int형인 pos를 체크하기에 부적절
  • 위와 같은 이유로 local에서 예시 입출력은 성공했지만, 사이트 제출 결과는 time over
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node {
    int pos;
    int count;
    Node1 lt,rt;

    public Node(int val, int count) {
        this.pos = val;
        this.count = count;
        lt=rt=null;
    }
}

public class Main {

    static int s;
    static int f;
    static List<Integer> check = new ArrayList<>();

    public static void bfs(Node node){
        Queue<Node> q = new LinkedList<>();
        q.offer(node);
        while(!q.isEmpty()){
            Node cur = q.poll();
            check.add(cur.pos);
            if(cur.pos == f){
                System.out.println(cur.count);
                return;
            }else{
                if(!check.contains(cur.pos+1))
                    q.offer(new Node(cur.pos + 1, cur.count + 1));
                if(!check.contains(cur.pos-1))
                    q.offer(new Node(cur.pos - 1, cur.count + 1));
                if(!check.contains(cur.pos+5))
                    q.offer(new Node(cur.pos + 5, cur.count + 1));
            }


        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        s = Integer.parseInt(input[0]);
        f = Integer.parseInt(input[1]);
        Node sNode = new Node(s,0);
        bfs(sNode);
    }
}

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int answer = 0;
    static int[] dis = {1, -1, 5};
    static boolean[] ch;
    static Queue<Integer> q = new LinkedList<>();

    public static int bfs(int s, int e) {
        ch = new boolean[10001];
        ch[s]=true;
        q.offer(s);
        int L=0;
        while(!q.isEmpty()){
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int cur = q.poll();
                if(e == cur)
                    return L;
                else{
                    for (int j = 0; j < 3; j++) {
                        int next = cur + dis[j];
                        if(0<=next && next <= 10000 && !ch[next]) {
                            q.offer(next);
                            ch[next] = true;
                        }
                    }
                }
            }
            L++;
        }
        return L;
    }

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int s = kb.nextInt();
        int e = kb.nextInt();
        System.out.println(bfs(s,e));
    }
}

오답 노트

  • 정답 코드와 내 코드 다른 부분을 정리
  • 정답 코드에서 챙겨야 할 부분 가져가기!
    • 1부터 10000까지이므로 이를 불변한 int[] 배열로 선언하여 표현
    • 현수의 이동할 수 있는 경우를 dis라는 배열로 표현하여 코드를 깔끔하게 표현
    • 이동한 곳의 수직선상 범위의 유효성 확인과 방문 했는지를 확인하여 중복 제거


문제 출처

자바(java) 알고리즘 문제풀이 :코딩테스트 대비

썸네일 출처

Image by storyset on Freepik

0개의 댓글