나는 미로에서 길 찾는 알고리즘은 BFS를 써왔다.
하지만 이문제는 일반 BFS와는 다르게 같은 지점을 여러번 방문 가능하다.
그렇다면 이 조건에서 길찾기 알고리즘을 어떻게 적용시켜야 할까?
제출코드
파이썬
import sys
sys.setrecursionlimit(5000)
from collections import deque
N, M = 0, 0
start = (0, 0)
end = (0, 0)
delta = [(1, 0, "d"), (0, -1, "l"), (0, 1, "r"), (-1, 0, "u")] # d, l, r, u
disMap = []
ans = ""
def solution(n, m, x, y, r, c, k):
global N, M, start, end, disMap
N, M = n, m
start = (x-1, y-1)
end = (r-1, c-1)
disMap = [[-1] * M for _ in range(N)]
disMap[r-1][c-1] = 0
DFS(x-1, y-1, "", k)
if ans == "":
return "impossible"
return ans
def DFS(ni, nj, word, dis):
global ans
if ans != "":
return
if disMap[ni][nj] == -1:
disMap[ni][nj] = findDistance(ni, nj)
if disMap[ni][nj] > dis or (dis - disMap[ni][nj]) % 2 == 1:
return
for di, dj, w in delta:
i = ni+di
j = nj+dj
if isRange(i, j) == False:
continue
if dis == 1 and (i, j) == end:
ans = word + w
return
DFS(i, j, word+w, dis-1)
def findDistance(i, j):
que = deque([(i, j, 0)])
visit = [[False] * M for _ in range(N)]
visit[i][j] = True
while que:
ni, nj, d = que.popleft()
for di, dj, w in delta:
i = ni+di
j = nj+dj
if isRange(i, j) and visit[i][j] == False:
if (i, j) == end:
return d+1
visit[i][j] = True
que.append((i, j, d+1))
def isRange(i, j):
if 0 <= i < N and 0 <= j < M :
return True
return False
자바
import java.util.*;
class Solution {
int N ;
int M ;
int[] start;
int[] end;
Object[][] delta = new Object[][]{{1, 0, "d"}, {0, -1, "l"}, {0, 1, "r"}, {-1, 0, "u"}};
int[][] disMap;
StringBuilder ans = new StringBuilder();
public String solution(int n, int m, int x, int y, int r, int c, int k) {
N = n;
M = m;
start = new int[]{x-1, y-1};
end = new int[]{r-1, c-1};
disMap = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
disMap[i][j] = -1;
}
}
disMap[r-1][c-1] = 0;
DFS(new Node(x-1, y-1, k));
if (ans.length() == 0) {
ans.append("impossible");
}
return ans.toString();
}
public void DFS(Node node) {
if (ans.length() != 0) {
return ;
}
int ni = node.i;
int nj = node.j;
int dis = node.dis;
if (disMap[ni][nj] == -1) {
disMap[ni][nj] = BFS(ni, nj);
}
if (disMap[ni][nj] > dis || (dis - disMap[ni][nj]) % 2 == 1) {
return ;
}
for (int idx = 0; idx < 4; idx ++) {
Node newNode = new Node(node, delta[idx], -1);
if (isRange(newNode) == false) {
continue ;
}
if (newNode.dis == 0 && endEqual(newNode) == true) {
ans = newNode.stringValue;
return ;
}
DFS(newNode);
}
}
public int BFS(int ni, int nj) {
Queue<Node> que = new LinkedList<>();
Node startNode = new Node(ni, nj, 0);
que.add(startNode);
boolean[][] visit = new boolean[N][M];
visit[ni][nj] = true;
while (que.size() != 0) {
Node now = que.poll();
for (int idx = 0; idx < 4; idx ++) {
Node newNode = new Node(now, delta[idx], 1);
if (isRange(newNode) && visit[newNode.i][newNode.j] == false) {
if (endEqual(newNode) == true) {
return newNode.dis;
}
visit[newNode.i][newNode.j] = true;
que.add(newNode);
}
}
}
return -1;
}
public boolean endEqual(Node node) {
if (end[0] == node.i && end[1] == node.j) {
return true;
}
return false;
}
public boolean isRange(Node node) {
int i = node.i;
int j = node.j;
if (0 <= i && i < N && 0 <= j && j < M) {
return true;
}
return false;
}
class Node {
int i;
int j;
int dis;
StringBuilder stringValue = new StringBuilder();
public Node(int i, int j, int dis) {
this.i = i;
this.j = j;
this.dis = dis;
}
public Node(Node node, Object[] deltaV, int d) {
this.i = node.i + (int)deltaV[0];
this.j = node.j + (int)deltaV[1];
this.dis = node.dis + d;
this.stringValue = new StringBuilder(node.stringValue);
stringValue.append((String)deltaV[2]);
}
public void plusWord(String w) {
stringValue.append(w);
}
}
}접근방법
DFS(ni, nj, word, dis)
우선 이 문제에선 DFS를 사용했다. 왜냐하면 이동방향의 순서를 사전순으로 뽑아야했기 때문에 너비 탐색보다는 깊이 탐색이 더 적절하다.
문제의 조건은 정확이 k를 이동해서 목적지까지 이동하는 것이다. 이를 위해서 같은 지점을 2번이상 방문하는 것도 가능하다. 즉, k를 만족하기 위해서라면 목적지와 멀어지는것도 가능하다.
여기서 백트래킹 요소가 들어간다.
1. 어디까지 멀어질 수 있을까?
나는 이 값을 disMap 배열을 만들어 확인했다. disMap[i][j]의 값은 (i, j)의 위치에서 목적지까지 최단 거리로 갈 수 있는 값이다. 즉, 멀어지더라도 남아있는 이동값 dis가 현재위치의 disMap 보다 크거나 같아야한다.
= disMap[ni][nj] > dis
2. 정확히 k를 이동해서 목적지 까지 도착못하는 경우는??
출발점 바로 오른쪽이 도착점이라고 생각해보자.
k = 1 인 경우 목적지 까지 갈 수 있을까? 갈 수 있다. 그냥 오른쪽으로 1번 이동하면 된다.
k = 2 인 경우는 어떨까?? 갈 수 없다. 목적지까지 이동하고 이동횟수가 1이 남는데 처리하고 목적지에 다시 올 방법이 없다.
k = 3 인 경우는?? 갈 수 있다. 목적지까지 이동후 이동횟수가 2가 남고, 이를 처리하기 위해 단순히 목적지에서 아무곳이나 이동하고 다시 목적지로 가면 된다.
k = 4 ?? 갈 수 없다. 목적지까지 이동하고 이동횟수가 3이 남고, 이를 처리하고 목적지에 다시 올 방법이 없다.
규칙이 보인다.
현재 위치에서 목적지까지 이동 후 남은 거리 dis - disMap[ni][nj] 의 값이 홀수면 정확히 k를 이동해 목적지로 갈 수가 없다.
= (dis - disMap[ni][nj]) % 2 == 1
자바 StringBuilder
저번에 배운대로 매번 이동방향을 기록하기 위해 StringBuilder를 사용했는데 이 문제를 통해 새로운 사실을 알았다.
StringBuilder s1 = new StringBuilder();
s1.append("gobeul");
System.out.println("s1 = " + s1.toString()); // gobeul
StringBuilder s2 = new StringBuilder();
s2 = s1;
System.out.println("s2 = " + s2.toString());
System.out.println("s1 에 글씨 추가");
s1.append("짱!!");
System.out.println("s1 = " + s1.toString()); // gobeul짱!!
System.out.println("s2 = " + s2.toString()); // ??이 경우 s2에 어떤값이 올 까?
나는 "gobeul"값을 기대했는데 실제 동작을 시켜보면 gobeul짱!! 이 온다.
파이썬의 복사처럼 s1 = s2가 주소값을 할당시키는 것 같다.
따라서 s1과 s2를 독립적으로 동작시키기 위해서
s2 = new StringBuilder(s1); 처럼 새로운 객체를 생성해야한다.
this.stringValue = new StringBuilder(node.stringValue);
stringValue.append((String)deltaV[2]);자바 배열비교
자바에서 두개의 배열안에 원소값이 같은지 확인할때 자바는 어떻게 하는지에 대해서도 배웠다.
파이썬은
a = [1, 2]
b = [1, 2]
print(a==b)이 경우 True 를 출력한다.
하지만 자바에서
int[] a = new int[]{1, 2};
int[] b = new int[]{1, 2};
System.out.println(a == b);이 경우는 false 이다.
자바에서 두개의 배열이 같은 원소를 가지는지 비교하는 방법은 2가지다.
1. 반복문을 통해 모두 비교
2. Arrays.equals() 활용
Arrays.equals() 의 경우 배열 차원이 늘어나면 deepEquals()를 써야하고 원소가 내가 만든 객체라면 equals() 메서드와 hashCode() 메서드를 재정의해서 사용해야한다.
좀 더 공부가 필요해이니 지금은 1번 방법을 사용하기로 했다.
