쵼쥬
쵼쥬의 개발공부 TIL
쵼쥬
전체 방문자
오늘
어제
  • 분류 전체보기 (276)
    • 코딩테스트 (192)
      • [알고리즘] 알고리즘 정리 (7)
      • [백준] 코딩테스트 연습 (126)
      • [프로그래머스] 코딩테스트 연습 (59)
    • Spring (71)
      • [인프런] 스프링 핵심 원리- 기본편 (9)
      • [인프런] 스프링 MVC 1 (6)
      • [인프런] 스프링 MVC 2 (4)
      • [인프런] 실전! 스프링 부트와 JPA 활용1 (7)
      • [인프런] 실전! 스프링 부트와 JPA 활용2 (5)
      • [인프런] 실전! 스프링 데이터 JPA (7)
      • [인프런] 실전! Querydsl (7)
      • JWT (5)
      • [인프런] Spring Cloud (17)
      • [인프런] Spring Batch (4)
    • Java (6)
      • [Java8] 모던인자바액션 (4)
      • [부스트코스] 웹 백엔드 (2)
      • [패스트캠퍼스] JAVA STREAM (0)
    • CS (6)
      • 디자인 패턴과 프로그래밍 패터다임 (2)
      • 네트워크 (4)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • 프로그래머스
  • 부스트코스
  • 코딩테스트
  • BFS
  • Spring Data JPA
  • 비트마스킹
  • 누적합
  • 타임리프
  • jpa
  • spring
  • 인프런
  • 자바
  • 위클리 챌린지
  • 백준
  • 스프링
  • MVC
  • 백분
  • querydsl
  • 구현
  • 알고리즘

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
쵼쥬

쵼쥬의 개발공부 TIL

숨바꼭질 3 -13529번
코딩테스트/[백준] 코딩테스트 연습

숨바꼭질 3 -13529번

2021. 10. 3. 14:12


풀이 방법

2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다. 

Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다.

풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다. 

BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다. 

가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다.

 

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

class Node {
    private int N;
    private int sec;

    public Node(int n, int sec) {
        N = n;
        this.sec = sec;
    }

    public int getSec() {
        return sec;
    }

    public int getN() {
        return N;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int sec = 0;

        Boolean[] visited = new Boolean[100001];
        Arrays.fill(visited, false);

        Queue<Node> q = new LinkedList<>();
        Node node = new Node(N, 0);

        q.offer(node);
        visited[N] = true;

        while (!q.isEmpty()) {
            node = q.poll();
            N = node.getN();
            sec = node.getSec();

            if (N == K) {
                System.out.println(sec);
                return;
            }

            if (N * 2 <= 100000 && !visited[N * 2]) {
                q.offer(new Node(N * 2, sec));
                visited[N * 2] = true;
            }
            if (N - 1 >= 0 && !visited[N - 1]) {
                q.offer(new Node(N - 1, sec + 1));
                visited[N - 1] = true;
            }
            if (N + 1 <= 100000 && !visited[N + 1]) {
                q.offer(new Node(N + 1, sec + 1));
                visited[N + 1] = true;
            }
        }
    }
}
import java.io.*;
import java.sql.Array;
import java.util.*;

class Node implements Comparable<Node> {
    private int N;
    private int sec;

    public Node(int n, int sec) {
        N = n;
        this.sec = sec;
    }

    public int getSec() {
        return sec;
    }

    public int getN() {
        return N;
    }

    @Override
    public int compareTo(Node other) {
        if (this.sec < other.sec)
            return -1;
        return 1;
    }
}

public class Main {

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static Boolean[] visited = new Boolean[100001];
    static int[] sec = new int[100001];
    static int K, N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        Arrays.fill(visited, false);
        Arrays.fill(sec, (int) 1e9);

        for (int i = 0; i <= 100000; i++) {
            graph.add(new ArrayList<Node>());
        }

        for (int i = 0; i <= 100000; i++) {
            if (i != 0 && i * 2 <= 100000)
                graph.get(i).add(new Node(i * 2, 0));
            if (i + 1 <= 100000)
                graph.get(i).add(new Node(i + 1, 1));
            if (i - 1 >= 0)
                graph.get(i).add(new Node(i - 1, 1));
        }

        dijkstra(N);
        System.out.println(sec[K]);
    }

    public static void dijkstra(int N) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(N, 0));
        sec[N] = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int index = node.getN();

            if (visited[index])
                continue;

            visited[index] = true;

            for (int i = 0; i < graph.get(index).size(); i++) {
                int x = sec[index] + graph.get(index).get(i).getSec();
                if (x < sec[graph.get(index).get(i).getN()]) {
                    sec[graph.get(index).get(i).getN()] = x;
                    q.offer(new Node(graph.get(index).get(i).getN(), x));
                }
            }
        }
    }
}

'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글

뒤집기 II - 1455번  (0) 2021.10.04
알바생 강호 - 1758번  (0) 2021.10.04
DFS와 BFS - 1260번  (0) 2021.10.02
저울 - 10159번  (0) 2021.10.01
백도어 - 17396번  (0) 2021.10.01
    '코딩테스트/[백준] 코딩테스트 연습' 카테고리의 다른 글
    • 뒤집기 II - 1455번
    • 알바생 강호 - 1758번
    • DFS와 BFS - 1260번
    • 저울 - 10159번
    쵼쥬
    쵼쥬

    티스토리툴바