[Java] 백준 16928.뱀과사다리게임

➡️문제 링크

https://www.acmicpc.net/problem/16928

 

 

💡아이디

플레이어는 주사위를 굴려 나온 수만큼 이동

도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다

-> 그래프 탐색이다

 

100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값

-> 최솟값이니까 bfs 아닐까?

 

이 과정을 거쳐 이 문제는 bfs로 풀어야겠다고 생각했다

 

처음에는 2차원 배열을 만들어 접근하려고 했다.

그런데 풀다보니 꼭! 2차워 배열로, 해당 숫자의 위치를 정확하게 알아야 이 문제를 풀 수 있는 걸까? 이렇게 접근하는 게 이 문제의 의도일까? 이런 생각이 들어 풀다가 우선 다 지웠다.

문제의 예제에서는 단순하게 숫자만 주는 것을 보며 이 문제는 1차원 배열로도 충분히 풀 수 있다고 생각했다.

 

그렇지만 그 다음 난관이 기다리고 있었다.

"그래서 뭐 어떻게 할 건데? 최솟값 루트를 바로 구할 수 있어?"

어떻게 해야 최솟값을 구할 수 있을까? 한 번에 착착착 구할 수 있나?

일단 완-탐으로 돌려버려야 하나? for 문 열심히 돌려볼까?

사다리는 무조건 타는 게 맞나? 만약 지금 사다리를 탔는데 알고보니 그 다다음 사다리가 더 먼저 도착하는 거라면? 가지치기 문제인가?

이라는 생각들이 자꾸 들며 갈피를 잡지 못했다.

 

그러다,

처음 위치는 무조건 1번에서 시작이라는 조건을 다시 보고 방향을 잡았다.

1. 1번에서 시작하면

2. 일단 착실하게 주사위를 돌리며 이동하고

3. 그 사이사이, 사다리나 뱀이 등장한다면 착실하게 타기

4. 그러다 100번 도착하면 최솟값 끝!

 

이걸 다시 정리하자면

1. 1번 위치 시작

2. for문을 돌려 현재 위치에서 1~6까지 더해서 위치 이동하기

3. 해당 위치가 사다리, 뱀이라면 이동하기

4. 만약 도달한 위치가 100번이라면 종료.

 

결국 그동안 많이 풀었던 (x, y) 2차원 배열을 이용해서 bfs 돌리는 문제에서

2차원 배열을 1차원으로 바꿔 생각하기만 하면 됐었다

그럼 풀어볼게요

 

 

✏️문제 풀이

1. bfs, HashMap 2개 -  성공 

처음에는 사디리와 뱀의 위치를 List로 저장해 bfs 돌리다

현재 위치가 사다리 or 뱀이라면 이동하도록 구현했다.

하지만, 사디리 or 뱀이라는 것을 확인해도 그 다음 어디로 가야할지를 각각의 list에서 찾아야 하는데, 이게 난관이었다...ㅋ

왜냐하면 Point 객체를 이용해서 (start, end, cost)를 저장했는데 이 end를 알기 위해서는 결국 list를 순차탐색해야했기 때문이었다.

이건 아니다! 싶어 빠르게 hashmap으로 방향을 돌렸고 결과는 성공!

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

public class Main {
	static class Point{
		int point;
		int cost;
		
		public Point(int point, int cost) {
			this.point = point;
			this.cost = cost;
		}
	}
	
	static HashMap<Integer, Integer> ladder = new HashMap<>();
	static HashMap<Integer, Integer> snake = new HashMap<>();
	static int [] dice = {1, 2, 3, 4, 5, 6};
	static int [] nums;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		nums = new int[101];
		
		// 사다리 위치
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			nums[start] = 1;	// 사다리
			ladder.put(start, end);
		}
		
		// 뱀 위치
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			nums[start] = 2;	// 뱀
			snake.put(start, end);
		}
		
		// 구현 및 출력
		System.out.println(bfs());
		
	}
	
	static int bfs() {
		Queue<Point> que = new LinkedList<>();
		que.add(new Point(1, 0));	// 초기 위치
		boolean [] visited = new boolean[101];
		int result = Integer.MAX_VALUE;
		
		while(!que.isEmpty()) {
			Point p = que.poll();
			
			if(p.point == 100) {		// 탈출구 도착
				result = p.cost;
//				result = Math.min(result, p.cost);
				break;
			}
			
			for(int i = 0; i < 6; i++) {
				int tx = p.point + dice[i];	// 주사위 이동
				
				if((tx >= 0 && tx <= 100) && !visited[tx]) {	// 범위 내 + 아직 방문 전
					if(nums[tx] == 1) {		// 사다리인 경우
						que.add(new Point(ladder.get(tx), p.cost + 1));
					}else if(nums[tx] == 2) {	// 뱀인 경우
						que.add(new Point(snake.get(tx), p.cost + 1));
					}else {
						que.add(new Point(tx, p.cost+1));	// 아무것도 없는 경우 - > 그냥 이동
					}
					visited[tx] = true;
				}
			}
		}
		
		return result;
	}

}

 

 

2.  bfs, HashMap 1개 - 성공

다른 사람들의 풀이를 보니 hashmap을 안 쓰고도 풀 수 있었고

내 풀이에서 굳이 사다리와 뱀 케이스를 나누어 HashMap을 저장하지 않아도 된다는 것을 깨달았다.

하나의 hashmap만을 만들어 그 안에 사디라와 뱀 케이스를 모두 저장했고, 

bfs를 돌리면 이동한 위치를 key로 가정해 존재여부를 판다해 존재한다면 value값으로 이동하도록 했다

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

public class Main {
	static class Point{
		int point;
		int cost;
		
		public Point(int point, int cost) {
			tahis.point = point;
			this.cost = cost;
		}
	}
	
	static HashMap<Integer, Integer> info = new HashMap<>();
	static int [] dice = {1, 2, 3, 4, 5, 6};
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 사다리 위치
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			info.put(start, end);
		}
		
		// 뱀 위치
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			info.put(start, end);
		}
		
		// 구현 및 출력
		System.out.println(bfs());
		
	}
	
	static int bfs() {
		Queue<Point> que = new LinkedList<>();
		que.add(new Point(1, 0));	// 초기 위치
		boolean [] visited = new boolean[101];
		int result = Integer.MAX_VALUE;
		
		while(!que.isEmpty()) {
			Point p = que.poll();
			
			if(p.point == 100) {		// 탈출구 도착
				result = p.cost;
//				result = Math.min(result, p.cost);
				break;
			}
			
			for(int i = 0; i < 6; i++) {
				int tx = p.point + dice[i];	// 주사위 이동
				
				if((tx >= 0 && tx <= 100) && !visited[tx]) {	// 범위 내 + 아직 방문 전
					if(info.containsKey(tx)) {
						que.add(new Point(info.get(tx), p.cost + 1));
					}else {
						que.add(new Point(tx, p.cost+1));	// 아무것도 없는 경우 - > 그냥 이동
					}
					visited[tx] = true;
				}
			}
		}
		
		return result;
	}

}

 

 

 

 

 

풀고나서 시간이 생각보다 많이 빨라 오! 싶었는데

내역을 보니 내 풀이가 10위 안에 들었다!!

보면서도 믿기지 않았다

맞힌사람 2972명 중 8등에 해당되는 풀이라니!(지피티한테 물어보니 상위 1% 안에 든다고 한다ㅎ)

물론,

시간과 메모리 기준이어서 "정말 퀄리티 높은 풀이다!" 라고 하긴 어렵겠지만

항상 코테에 자신감이 부족한 나에게는 엄청난 발전이자 변화다

이 기억, 이 마음가짐 그대로

앞으로 열심히 풀어서

올해는 코테도 척척 뚫고 정말 꼭!!!! 취업해야지

화이팅!