728x90
문제
* X : 현재 숫자
* K : 목표 숫자
* 조건 : X-1 또는 X+1 또는 X*2 가능
* 출력 : 최소 도달 cnt와 최소 도달 방법 수
문제 링크 : https://www.acmicpc.net/problem/12851
원리
이 문제는 BFS의 중복을 일부 혀용해 주는 경우가 핵심
즉, 기본적으로 중복 방문은 허용하지 않되, 중간 루트에 같은 시간을 소요해서 같은 위치에 도착한 경우의 중복은 허용
풀이방법
* 1. BFS로 최소 도달 시간을 구함
* 2. 최소 도달 시간과 같은 시간에 도달하는 경우를 cnt
나의 코드
1. [실패] 첫 시도 : BFS로 최소시간 구하기는 성공. 최소 경로 개수 count 실패.
: Recur부분에서 무한 루프에 빠짐
더보기
private static int X;
private static int K;
private static int sec;
private static int cnt;
private static boolean[] visited = new boolean[100001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
X = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
sec = 0;
cnt = 0;
BFS(); // 최소 시간 구하기
visited = new boolean[100001];
Recur(X);
// BFS2();
bw.write(""+sec+"\n");
bw.write(""+cnt+"\n");
bw.close();
}
/**
* 최소 시간을 구하는 BFS
*/
private static void BFS() {
Deque<Check> dq = new ArrayDeque<>();
dq.add(new Check(X,0));
visited[X] = true;
while(!dq.isEmpty()) {
Check check = dq.poll();
int now = check.Now;
int nowSec = check.Sec;
if(now==K) {
sec = nowSec; // 가장 먼저 도달하는 check의 cnt는 가장 적다.
break;
}
for(int i=0 ; i<3 ; i++) {
if(i==0 && !visited[now-1]) {
dq.add(new Check(now-1, nowSec+1));
visited[now-1] = true;
}
else if(i==1 && !visited[now+1]) {
dq.add(new Check(now+1, nowSec+1));
visited[now+1] = true;
}
else if(i==2 && !visited[now*2]) {
dq.add(new Check(now*2, nowSec+1));
visited[now*2] = true;
}
}
}
}
private static class Check {
private int Now;
private int Sec;
public Check (int now, int sec) {
this.Now = now;
this.Sec = sec;
}
}
private static void Recur (int now) {
if(now==K)
cnt++;
else {
if(0<=now && now<=100000) {
for(int i=0 ; i<3 ; i++) {
if(i==0 && now-1>=0 && !visited[now-1]) {
Recur(now-1);
visited[now-1] = true;
}
else if (i==1 && now+1<=0 && !visited[now+1]) {
Recur(now+1);
visited[now+1] = true;
} else if (i==2 && now*2<=0 && !visited[now*2]) {
Recur(now*2);
visited[now*2] = true;
}
}
}
}
}
2. [실패] BFS를 두번 사용한 방법으로, 두 번째 BFS의 객체는 각자의 visited[]를 갖도록 설정
: 통합 visited를 사용하자니, 중간만 경로가 겹치는 다른 루트가 count 되지않기 때문
더보기
private static int X;
private static int K;
private static int sec;
private static int cnt;
private static boolean[] visited = new boolean[100001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
X = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
sec = 0;
cnt = 0;
BFS(); // 최소 시간 구하기
visited = new boolean[100001];
BFS2();
bw.write(""+sec+"\n");
bw.write(""+cnt+"\n");
bw.close();
}
/**
* 최소 시간을 구하는 BFS
*/
private static void BFS() {
Deque<Check> dq = new ArrayDeque<>();
dq.add(new Check(X,0));
visited[X] = true;
while(!dq.isEmpty()) {
Check check = dq.poll();
int now = check.Now;
int nowSec = check.Sec;
if(now==K) {
sec = nowSec; // 가장 먼저 도달하는 check의 cnt는 가장 적다.
break;
}
for(int i=0 ; i<3 ; i++) {
if(i==0 && !visited[now-1]) {
dq.add(new Check(now-1, nowSec+1));
visited[now-1] = true;
}
else if(i==1 && !visited[now+1]) {
dq.add(new Check(now+1, nowSec+1));
visited[now+1] = true;
}
else if(i==2 && !visited[now*2]) {
dq.add(new Check(now*2, nowSec+1));
visited[now*2] = true;
}
}
}
}
private static class Check {
private int Now;
private int Sec;
public Check (int now, int sec) {
this.Now = now;
this.Sec = sec;
}
}
private static void BFS2() {
Deque<Check2> dq = new ArrayDeque<>();
boolean[] visited2 = new boolean[100001];
visited2[X] = true;
dq.add(new Check2(X,0,visited2));
while(!dq.isEmpty()) {
Check2 check = dq.poll();
int now = check.Now;
int nowSec = check.Sec;
if(now==K && nowSec==sec) {
cnt++;
}
for(int i=0 ; i<3 ; i++) {
if(i==0 && now-1>=0 && !check.Visited[now-1]) {
boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
nowVisited[now-1] = true;
dq.add(new Check2(now-1, nowSec+1, nowVisited));
}
else if(i==1 && now+1<100001 && !check.Visited[now+1]) {
boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
nowVisited[now+1] = true;
dq.add(new Check2(now+1, nowSec+1, nowVisited));
}
else if(i==2 && now*2<100001 && !check.Visited[now*2]) {
boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
nowVisited[now*2] = true;
dq.add(new Check2(now*2, nowSec+1, nowVisited));
}
}
}
}
private static class Check2 {
private int Now;
private int Sec;
private boolean[] Visited;
public Check2 (int now, int sec, boolean[] visited) {
this.Now = now;
this.Sec = sec;
this.Visited = visited;
}
}
3. [성공] 사실상 레퍼런스를 이해한 후 따라친 코드
private static int X;
private static int K;
private static int sec = Integer.MAX_VALUE;
private static int cnt = 0;
private static int[] visited = new int[100001]; // 단순 방문체크가 아닌, 방문 했을 떄 시간을 비교하기 위해 int형으로 사용
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
X = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 만약 X가 K보다 크면, 최소루트는 -1을 반복하는 방법밖에 없음
if(X>=K) {
System.out.println(X-K + "\n" + 1);
return;
}
// X가 K보다 작은 경우
BFS();
bw.write(""+sec+"\n");
bw.write(""+cnt+"\n");
bw.close();
}
/**
* 최소 시간을 구하는 BFS
*/
private static void BFS() {
Deque<Integer> dq = new ArrayDeque<>();
dq.add(X);
visited[X] = 1;
while(!dq.isEmpty()) {
int now = dq.poll();
// 현재 방문 시간이 최소시간보다 큰데 아직 도착을 못했으면, 이미 최소가 아닌거임
if(sec < visited[now]) return;
// 각 연산방식을 순차적으로 적용해 주기 위한 반복문
for(int i=0 ; i<3 ;i++) {
int next = 0;
if(i==0) next = now - 1;
else if(i==1) next = now + 1;
else next = now * 2;
if(next<0 || next> 100000) continue; // 범위를 벗어나면 제낌
if(next == K) {
sec = visited[now]; // 처음 K에 도달한 경우 최소시간이 대입되며, 그 이후는 이미 위에서 최소시간을 넘어가는 경우에서 걸러짐
cnt++; // 이후 같은 시간안에 도착하는 경우마다 cnt++;
}
// 만약 첫 방문이거나, 다른 경우랑 중복도착했더라도 같은 시간이 걸린 경우 (중복을 허용해 주어야 하는 경우)
if(visited[next] == 0 || visited[next] == visited[now] + 1) {
dq.add(next); // 다음 계산 해준다.
visited[next] = visited[now] + 1; // 다음 방문할 곳에 경과한 시간을 체크해 주며, 최소시간일 때로 유지된다.
}
}
}
}
레퍼런스 코드
참고 링크 : 뱀귤님의 블로그
static int N, K;
static int[] time = new int[100001];
static int minTime = 987654321;
static int count = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if (N >= K) {
System.out.println((N-K) + "\n1");
return;
}
bfs();
System.out.println(minTime + "\n" + count);
}
static void bfs() {
Queue<Integer> q = new LinkedList<Integer>();
q.add(N);
time[N] = 1;
while (!q.isEmpty()) {
int now = q.poll();
// now 방문 시간이 최소 시간보다 크면 뒤는 더 볼 필요 없음
if (minTime < time[now]) return;
for (int i=0; i<3; i++) {
int next;
if (i == 0) next = now + 1;
else if (i == 1) next = now - 1;
else next = now * 2;
if (next < 0 || next > 100000) continue;
if (next == K) {
minTime = time[now];
count++;
}
// 첫 방문이거나 (time[next] == 0)
// 이미 방문한 곳이어도 같은 시간에 방문했다면 (time[next] == time[now] + 1)
// 경우의 수에 추가될 수 있기 때문에 Queue 에 한번 더 넣어줌
if (time[next] == 0 || time[next] == time[now] + 1) {
q.add(next);
time[next] = time[now] + 1;
}
}
}
}
Chat GPT 코드
[실패] 시작부터 싸하긴 했지만.. 얘는 왜이렇게 자신감이 넘치는 걸까..?

더보기


문제 번호까지 알려줬지만 틀려주는 우리 쥐피티

import java.util.*;
public class Main {
static int N, K, count = 0, time = Integer.MAX_VALUE;
static boolean[] visited = new boolean[100001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
bfs();
System.out.println(time);
System.out.println(count);
}
public static void bfs() {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(N, 0));
visited[N] = true;
while(!queue.isEmpty()) {
Node current = queue.poll();
visited[current.position] = true;
if(current.position == K) {
time = current.time;
count++;
continue;
}
if(current.position - 1 >= 0 && !visited[current.position - 1]) {
queue.add(new Node(current.position - 1, current.time + 1));
}
if(current.position + 1 <= 100000 && !visited[current.position + 1]) {
queue.add(new Node(current.position + 1, current.time + 1));
}
if(current.position * 2 <= 100000 && !visited[current.position * 2]) {
queue.add(new Node(current.position * 2, current.time + 1));
}
}
}
static class Node {
int position;
int time;
public Node(int position, int time) {
this.position = position;
this.time = time;
}
}
}

728x90
'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글
| [백준] no12865: 평범한 배낭 - DP (0) | 2023.05.21 |
|---|---|
| [백준] no1504: 특정한 최단 경로 - 다익스트라 (0) | 2023.05.18 |
| [백준] no9465: 스티커 (0) | 2023.05.09 |
| [백준] no1043: 거짓말 - 그래프 탐색 (2) | 2023.05.06 |
| [백준] no11053: 가장 긴 증가하는 부분 수열 - 최장 증가 부분 수열 (LIS) (0) | 2023.05.05 |