문제링크
풀이방법
어렵지만 재미있는 문제였다! 원래는 풀이 #1으로 풀었는데, 다른 풀이를 보다가 재미있는 풀이방법을 봐서 그 방법으로도 구현해봤다.
풀이 #1
처음에는 BFS 문제인가? 싶었다. 근데 문제를 다시보니 백조가 만나는 시간이 아니라 백조가 빙하가 녹아서 언제 같은 영역안에 있게 되는지 물어보는 문제였다! '영역'이라고 하니까 Union-Find가 생각났다. 이걸로 충분히 풀 수 있을거 같아서 시작했는데, 이 전까지 풀어본 Union-Find에 비해 구현난이도가 아주 빡셌다; 풀면서 이게 맞나 싶었는데 결국 구현했다..!!!!
일단 Tree를 초기화 했어야 했다. LakePosition 이차원배열을 Tree로 설정하고 초기에 물이 있는 부분이면 주변(위, 아래, 오른쪽, 왼쪽) 물과 union 연산을 진행했다. 이렇게 초기화를 끝냈고, 그 다음 단계는 크게 말하면 녹는 빙하를 그 주위의 물인 부분들과 union 연산을 하는거다. 근데 여기서 녹는 빙하를 찾는 게 시간초과 해결의 답이었다! 원래는 빙하를 큐에 넣고 큐를 돌면서 녹지 못하는 부분이면 큐에 다시 넣는 방식을 채택했다. 시간초과가 발생했고, 생각을 바꿔봤다. 물인 부분을 큐에 넣어 그에 맞닿아 있는 빙하를 녹이고 물이 된 그 부분을 큐에 다시 넣는 방식을 생각했다. 이렇게 하니 시간초과가 해결되었다! 이렇게 하루 안에 녹는 빙하를 처리하고 백조들이 같은 영역에 있는지 find 연산을 통해 확인했다.
코드
class Solution3197 {
int r, c;
char[][] lake;
LakePosition swanA;
LakePosition swanB;
Queue<LakePosition> landQ;
LakePosition[][] tree;
final LakePosition ROOT = new LakePosition(-1, -1);
final int[] dy = {0, 0, +1, -1};
final int[] dx = {+1, -1, 0, 0};
Solution3197(int r, int c, char[][] lake, LakePosition swanA, LakePosition swanB, Queue<LakePosition> landQ) {
this.r = r;
this.c = c;
this.lake = lake;
this.swanA = swanA;
this.swanB = swanB;
this.landQ = landQ;
initTree();
}
int getMinTime() {
int time = 0;
while (true) {
int qSize = landQ.size();
while (--qSize >= 0) {
LakePosition head = landQ.poll();
for (int i = 0; i < 4; i++) {
int nextY = head.y + dy[i];
int nextX = head.x + dx[i];
if (isInRange(nextY, nextX) && lake[nextY][nextX] == 'X') {
lake[nextY][nextX] = '.';
landQ.offer(new LakePosition(nextY, nextX));
merge(head.y, head.x, nextY, nextX);
for (int j = 0; j < 4; j++) {
int neighborY = nextY + dy[j];
int neighborX = nextX + dx[j];
if (isInRange(neighborY, neighborX) && lake[neighborY][neighborX] == '.') merge(nextY, nextX, neighborY, neighborX);
}
}
}
}
time++;
if (find(swanA.y, swanA.x).equals(find(swanB.y, swanB.x))) break;
}
return time;
}
void initTree() {
tree = new LakePosition[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (lake[i][j] == '.') {
tree[i][j] = ROOT;
for (int d = 0; d < 4; d++) {
int neighborY = i + dy[d];
int neighborX = j + dx[d];
if (isInRange(neighborY, neighborX) && lake[neighborY][neighborX] == '.') merge(i, j, neighborY, neighborX);
}
}
}
}
}
LakePosition find(int y, int x) {
if (tree[y][x] == null) return null;
if (tree[y][x].equals(ROOT)) return new LakePosition(y, x);
else {
tree[y][x] = find(tree[y][x].y, tree[y][x].x);
return tree[y][x];
}
}
void merge(int aY, int aX, int bY, int bX) {
LakePosition rootA = find(aY, aX);
LakePosition rootB = find(bY, bX);
if (rootA == null) tree[aY][aX] = rootB;
else if (rootB == null) tree[bY][bX] = rootA;
else if (!rootA.equals(rootB)) tree[rootA.y][rootA.x] = rootB;
}
boolean isInRange(int y, int x) {
return ((y >= 0) && (y < r) && (x >= 0) && (x < c));
}
}
class LakePosition {
int y;
int x;
LakePosition(int y, int x) {
this.y = y;
this.x = x;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
LakePosition otherObj = (LakePosition) obj;
return (this.y == otherObj.y) && (this.x == otherObj.x);
}
@Override
public int hashCode() {
return Objects.hash(y, x);
}
@Override
public String toString() {
return "Y: " + y + ", X: " + x;
}
}풀이 #2
두번째 방법은 BFS와 이분탐색을 이용하는 방법이다. BFS는 두 부분에 쓰이게 되는데, 첫번째는 빙하가 녹는 시점을 저장할 때 쓰인다. 그리고 이분탐색을 통해 timeLimit 값을 전달하면 그 날이 경과하면 두 백조가 만날 수 있는지 확인하는 데 쓰인다.
빙하가 녹는 시점은 한 번의 BFS를 통해 확인한다. 빙하가 어떤 물에 의해 녹게 되면 그 물이 녹은 시점에 + 1을 해 해당 빙하가 녹는 시점을 구할 수 있다. 이분탐색 시에 start와 end 값을 갖게 되는데, end 값은 빙하가 녹는 시점 중 가장 큰 값을 저장해 이용한다. 끝!
코드
class Solution3197_BFS {
int r, c;
char[][] lake;
LakePosition swanA;
LakePosition swanB;
Queue<LakePosition> landQ;
int[][] meltingTime;
int lastMeltingTime = 0;
final int[] dy = {0, 0, +1, -1};
final int[] dx = {+1, -1, 0, 0};
Solution3197_BFS(int r, int c, char[][] lake, LakePosition swanA, LakePosition swanB, Queue<LakePosition> landQ) {
this.r = r;
this.c = c;
this.lake = lake;
this.swanA = swanA;
this.swanB = swanB;
this.landQ = landQ;
initMeltingTime();
}
void initMeltingTime() {
meltingTime = new int[r][c];
while (!landQ.isEmpty()) {
LakePosition head = landQ.poll();
for (int i = 0; i < 4; i++) {
int nextY = head.y + dy[i];
int nextX = head.x + dx[i];
if (isInRange(nextY, nextX) && lake[nextY][nextX] == 'X') {
lake[nextY][nextX] = '.';
landQ.offer(new LakePosition(nextY, nextX));
meltingTime[nextY][nextX] = meltingTime[head.y][head.x] + 1;
if (lastMeltingTime < meltingTime[nextY][nextX]) lastMeltingTime = meltingTime[nextY][nextX];
}
}
}
}
int getMinTime() {
int startTime = 0;
int endTime = lastMeltingTime;
while ((endTime - startTime) > 1) {
int midTime = (startTime + endTime) / 2;
if (isSwanInSameArea(midTime)) endTime = midTime;
else startTime = midTime;
}
return endTime;
}
boolean isSwanInSameArea(int time) {
Queue<LakePosition> areaQ = new LinkedList<>();
boolean[][] visited = new boolean[r][c];
areaQ.offer(swanA);
visited[swanA.y][swanA.x] = true;
while (!areaQ.isEmpty()) {
LakePosition head = areaQ.poll();
for (int i = 0; i < 4; i++) {
int nextY = head.y + dy[i];
int nextX = head.x + dx[i];
if (isInRange(nextY, nextX) && !visited[nextY][nextX] && meltingTime[nextY][nextX] <= time) {
visited[nextY][nextX] = true;
LakePosition nextPos = new LakePosition(nextY, nextX);
areaQ.offer(nextPos);
if (nextPos.equals(swanB)) return true;
}
}
}
return false;
}
boolean isInRange(int y, int x) {
return ((y >= 0) && (y < r) && (x >= 0) && (x < c));
}
}
똑딱똑딱