공부 기록

먼저, 브루트포스로 모든 점에 대해 DFS를 돌려 가장 긴 path를 찾는 방법이 있을 것이다. 하지만 이 방법의 경우 시간초과가 발생한다.

class Solution {
	public static int[] dr = { 1, -1, 0, 0 };
	public static int[] dc = { 0, 0, 1, -1 };

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int answer = 0;
		for (int i = 0; i < maxRow; ++i)
			for (int j = 0; j < maxCol; ++j)
				answer = Math.max(answer, dfs(matrix, i, j, maxRow, maxCol));
		return answer;
	}

	private int dfs(int[][] matrix, int row, int col, int maxRow, int maxCol) {
		int ans = 0;
		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				ans = Math.max(ans, dfs(matrix, r, c, maxRow, maxCol));
			}
		}
		return ++ans;
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}

위 코드에서 시간을 줄일 수 있는 부분은 어디일까? 위 코드에서 중복되는 부분은 dfs로 계산하여 max를 업데이트 하는 부분이다.

이 부분을 줄이기 위해 모든 점에 대해 가장 긴 path를 찾는 도중에 이미 갔던 길의 경우는 저장해 두고,

다시 방문할 때 저장했던 길이를 바로 리턴해주면 더 효율적일 것이다. => 메모이제이션

class Solution {
	public static int[] dr = { 1, -1, 0, 0 };
	public static int[] dc = { 0, 0, 1, -1 };

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int[][] memo = new int[maxRow][maxCol];

		int answer = 0;
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				answer = Math.max(answer, dfs(matrix, memo, i, j, maxRow, maxCol));
			}
		}
		return answer;
	}

	public int dfs(int[][] matrix, int[][] memo, int row, int col, int maxRow, int maxCol) {
		if (memo[row][col] != 0) {
			return memo[row][col];
		}

		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				memo[row][col] = Math.max(memo[row][col], dfs(matrix, memo, r, c, maxRow, maxCol));
			}
		}

		memo[row][col]++;
		return memo[row][col];
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}

수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다.

• 수빈이가 움직이는 방법: X - 1, X + 1, 2 * X
• 동생이 움직이는 방법: K + 1 + 2 + 3 + ... + i
• 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

수빈이가 왼쪽한번 오른쪽한번 이동하게 되면 제자리로 돌아오기 때문에, 짝수/홀수 시간마다 갈 수 있는 곳을 나누어 시간을 저장한다.

만약 동생이 지나가는 좌표값에 수빈이가 처음 도착하는 시간이 더 빠를 경우 답을 업데이트 해 주도록 한다.

import java.util.*;

public class Main {
	public static int INF = 500000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int indexSubin = in.nextInt();
		int indexSister = in.nextInt();

		int isVisited[][] = new int[INF + 1][2];
		for (int i = 0; i <= INF; i++) {
			isVisited[i][0] = -1;
			isVisited[i][1] = -1;
		}

		moveSubin(isVisited, indexSubin);
		System.out.println(moveSister(isVisited, indexSister));
	}

	public static void moveSubin(int[][] isVisited, int start) {
		Queue<Move> queue = new LinkedList<Move>();
		queue.add(new Move(start, 0));
		isVisited[start][0] = 0;

		while (!queue.isEmpty()) {
			Move now = queue.poll();

			int nextTime = now.time + 1;
			checkBoundaryAndPushQueue(isVisited, queue, now.index - 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index + 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index * 2, nextTime);
		}
	}

	public static void checkBoundaryAndPushQueue(int[][] isVisited, Queue<Move> queue, int index, int time) {
		if (isBoundary(index) && isVisited[index][time % 2] == -1) {
			queue.add(new Move(index, time));
			isVisited[index][time % 2] = time;
		}
	}

	public static int moveSister(int[][] isVisited, int start) {
		for (int time = 0; time < INF; time++) {
			int index = start + time * (time + 1) / 2;

			if (index > INF) {
				return -1;
			}

			if (isVisited[index][time % 2] != -1 && isVisited[index][time % 2] <= time) {
				return time;
			}
		}
		return -1;
	}

	public static boolean isBoundary(int index) {
		if (index < 0) {
			return false;
		}
		if (index > INF) {
			return false;
		}
		return true;
	}
}

class Move {
	int index;
	int time;

	public Move(int index, int time) {
		this.index = index;
		this.time = time;
	}

	@Override
	public String toString() {
		return "(" + index + ": " + time + ")";
	}
}