[백준/Java] 2412: 암벽등반

문제: https://www.acmicpc.net/problem/2412

 

 

조건

• TimeLimit = 2s
• (0,0)에서 정상까지 등반할 때, 최소 이동 횟수는 얼마인가? 정상까지 이동할 수 없다면 -1을 출력
• (x,y)와 (a,b)에 대해 다음 조건을 만족하면 이동할 수 있다
  • |a-x| <=2, (0<= a <= 100만)
  • |b-y| <=2, (0<= b<=T<=20만)
• 암벽의 홈 개수는 최대 5만개

 

풀이

• 완전탐색
  • n이 최대 5만이므로 O(5만)으로 탐색 가능
    -> 격자 map의 한 변의 크기가 5만인게 아니라, 전체 탐색 가능한 좌표가 5만개임을 유의
  • 이동은 8방향으로, 길이가 1, 2인 상황을 모두 탐색해야한다
    -> 여기서 3차원 for문이 사용됨
    -> 1: 방향, 2: x좌표 이동거리, 3: y좌표 이동거리
    -> 따라서 8*2*2 = 32 
  • x, y좌표 범위가 너무 크기 때문에, 방문 체크에 사용할 visited를 int[x크기][y크기]로 선언할 수 없다. 따라서 다음 방법들을 생각해볼 수 있다
    1. 이차원 map 사용 -> visited = Map<x좌표(Integer), Map<y좌표, Boolean>>
    2. Set 사용 -> visited = Set<"x좌표, y좌표"(String)>
    3. 좌표 압축 사용 -> visited = new boolean[n] -> x 최댓값이 100만이고 y최댓값이 20만이지만, 최대 좌표 수가 5만개이기 때문에 각각을 5만개씩 압축할 수 있음. 하지만.. int[5만][5만] 배열은 이미 터지므로 해당 방법은 사용 불가능

 

코드1. 이차원 Map 사용

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

public class Main {

	static int n;
	static int t;
	static Map<Integer, Set<Integer>> map;
	static int minCnt;
	static Map<Integer, Map<Integer, Boolean>> visited;
	static int[] dr = { -1, 1, 0, 0, -1, -1, 1, 1}; // 상하좌우, 상좌, 상우, 하좌, 하우
	static int[] dc = { 0, 0, -1, 1, -1, 1, -1, 1}; // 상하좌우, 상좌, 상우, 하좌, 하우


	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		t = Integer.parseInt(st.nextToken());

		map = new HashMap<>();
		visited = new HashMap<>();
		visited.put(0, new HashMap<>());
		visited.get(0).put(0, true);

		for (int i=0; i<n; i++) {

			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			if (!map.containsKey(x)) map.put(x, new HashSet<>());
			map.get(x).add(y);

			if (!visited.containsKey(x)) visited.put(x, new HashMap<>());
			visited.get(x).put(y, false);
		}


		// bfs
		bfs();

		// result
		System.out.print(minCnt == 0 ? -1 : minCnt);
	}





	static void bfs() {

		// set-up
		Deque<Node> q = new ArrayDeque<>();
		q.add(new Node(0, 0, 0));

		// search
		while (!q.isEmpty()) {

			Node cur = q.pop();
			int curX = cur.x;
			int curY = cur.y;
			int curM = cur.move;

			if (curY == t) {
				minCnt = curM;
				break;
			}

			for (int i=0; i<8; i++) {
				for (int j=1; j<=2; j++) {
					for (int k=1; k<=2; k++) {

						int nx = curX + dr[i] * j;
						int ny = curY + dc[i] * k;

						// validate
						if (nx < 0 || nx > 1_000_000 || ny < 0 || ny > t) continue;
						if (!map.containsKey(nx) || !map.get(nx).contains(ny)) continue;
						if (Math.abs(curX - nx) > 2 || Math.abs(curY - ny) > 2) continue;
						if (visited.get(nx).get(ny)) continue;

						visited.get(nx).put(ny, true);
						q.add(new Node(nx, ny, curM + 1));
					}
				}
			}

		}
	}


	static class Node {

		int x;
		int y;
		int move;

		Node(int x, int y, int m) {
			this.x = x;
			this.y = y;
			this.move = m;
		}

	}

}

 

 

 

코드2. Set 사용

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

public class Main {

	static int n;
	static int t;
	static Set<String> map;
	static int minCnt;
	static Set<String> visited;
	static int[] dr = { -1, 1, 0, 0, -1, -1, 1, 1}; // 상하좌우, 상좌, 상우, 하좌, 하우
	static int[] dc = { 0, 0, -1, 1, -1, 1, -1, 1}; // 상하좌우, 상좌, 상우, 하좌, 하우


	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		t = Integer.parseInt(st.nextToken());

		map = new HashSet<>();
		for (int i=0; i<n; i++) {

			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map.add(x + "," + y);
		}


		// bfs
		visited = new HashSet<>();
		bfs();

		// result
		System.out.print(minCnt == 0 ? -1 : minCnt);
	}





	static void bfs() {

		// set-up
		Deque<Node> q = new ArrayDeque<>();
		q.add(new Node(0, 0, 0));
		visited.add("0,0");

		// search
		while (!q.isEmpty()) {

			Node cur = q.pop();
			int curX = cur.x;
			int curY = cur.y;
			int curM = cur.move;

			if (curY == t) {
				minCnt = curM;
				break;
			}

			for (int i=0; i<8; i++) {
				for (int j=1; j<=2; j++) {
					for (int k=1; k<=2; k++) {

						int nx = curX + dr[i] * j;
						int ny = curY + dc[i] * k;

						// validate
						String key = nx + "," + ny;
						if (nx < 0 || nx > 1_000_000 || ny < 0 || ny > t) continue;
						if (!map.contains(key)) continue;
						if (Math.abs(curX - nx) > 2 || Math.abs(curY - ny) > 2) continue;
						if (visited.contains(key)) continue;

						visited.add(key);
						q.add(new Node(nx, ny, curM + 1));
					}
				}
			}

		}
	}


	static class Node {

		int x;
		int y;
		int move;

		Node(int x, int y, int m) {
			this.x = x;
			this.y = y;
			this.move = m;
		}

	}

}