접근
푸는데 정말 오래걸린 문제였다..ㅠㅠ 다른 블로그의 솔루션들과 아무리 비교해봐도 똑같은데 자꾸 메모리 초과가 나는 것이다. 그래서 혹시나하고 솔루션 코드를 돌려봤는데.. 똑같이 메모리 초과가 났다. 알고보니 불과 3일전(!)에 데이터가 추가되면서, 4142개 중 1475개의 기존 정답 코드가 메모리 초과가 되었더라😂
그래서 이 블로그의 솔루션 코드를 참고하여 통과할 수 있었다. 기존에는 2차원 배열에 해당 위치에 올 수 있는 거울의 최소 개수를 저장했었다. 그런데 통과한 코드에는 3차원 배열을 선언하여 방향까지 함께 고려해줘야 했다. 아마 추가된 데이터에서 같은 칸, 방향에 여러번 방문하는 경우가 있지 않을까 짐작해본다. 그런데 이상하게 내 코드에서는 현재 방향과 정반대의 경우 넘어가는 조건 Math.abs(now.dir - i) == 2 을 추가하면 틀리게 나온다.. 이유는 아직 모르겠지만 알게된다면 포스팅을 수정하러 오겠다.
코드
메모리 초과 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ6087 {
static class Pos implements Comparable<Pos> {
int x, y, mirrorCnt, dir;
public Pos(int x, int y, int mirrorCnt, int dir) {
this.x = x;
this.y = y;
this.mirrorCnt = mirrorCnt; // [x][y]에 도달하기 위해 필요한 거울의 개수
this.dir = dir;
}
@Override
public int compareTo(Pos o) {
return this.mirrorCnt - o.mirrorCnt;
}
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int INF = 100*100+1;
static int w, h;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값 저장
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
char[][] map = new char[h][w];
int[][] minCnt = new int[h][w];
Pos from = null, to = null;
for (int i = 0; i < h; i++){
map[i] = br.readLine().toCharArray();
for (int j = 0; j < w; j++) {
if(map[i][j] == 'C'){ // 시작 및 도착 위치
if(from == null) from = new Pos(i, j, -1, -1);
else to = new Pos(i, j, -1, -1);
}
}
}
// 결과 출력
System.out.println(bfs(from, to, map, minCnt));
}
private static int bfs(Pos from, Pos to, char[][] map, int[][] minCnt) {
PriorityQueue<Pos> pq = new PriorityQueue<>();
for (int i = 0; i < map.length; i++)
Arrays.fill(minCnt[i], INF);
// 시작지점 처리
pq.add(from);
minCnt[from.x][from.y] = 0;
// bfs
while(!pq.isEmpty()){
Pos cur = pq.poll();
// 도착지점 도달
if(cur.x == to.x && cur.y == to.y)
return cur.mirrorCnt;
// 거울 개수가 갱신되지 않는 경우 넘어감
if(minCnt[cur.x][cur.y] < cur.mirrorCnt) continue;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 범위를 벗어나거나 벽이면 넘어감
if(!inBound(nx, ny, w, h) || map[nx][ny] == '*') continue;
Pos next = new Pos(nx, ny, cur.mirrorCnt, d);
if(d != cur.dir) next.mirrorCnt++;
// 거울 개수가 갱신되지 않는 경우 넘어감
if(minCnt[nx][ny] < next.mirrorCnt) continue;
minCnt[nx][ny] = next.mirrorCnt;
pq.add(next);
}
}
return -1;
}
private static boolean inBound(int x, int y, int w, int h) {
return !(x < 0 || y < 0 || x >= h || y >= w);
}
}
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ6087 {
static class Pos implements Comparable<Pos> {
int x, y, mirrorCnt, dir;
public Pos(int x, int y, int mirrorCnt, int dir) {
this.x = x;
this.y = y;
this.mirrorCnt = mirrorCnt; // [x][y]에 도달하기 위해 필요한 거울의 개수
this.dir = dir;
}
@Override
public int compareTo(Pos o) {
return this.mirrorCnt - o.mirrorCnt;
}
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int INF = 100*100+1;
static int w, h;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값 저장
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
char[][] map = new char[h][w];
int[][][] visited = new int[4][h][w];
Pos from = null, to = null;
for (int i = 0; i < h; i++){
map[i] = br.readLine().toCharArray();
for (int j = 0; j < w; j++) {
if(map[i][j] == 'C'){ // 시작 및 도착 위치
if(from == null) from = new Pos(i, j, -1, -1);
else to = new Pos(i, j, -1, -1);
}
}
}
// 결과 출력
System.out.println(bfs(from, to, map, visited));
}
private static int bfs(Pos from, Pos to, char[][] map, int[][][] visited) {
PriorityQueue<Pos> pq = new PriorityQueue<>();
for (int d = 0; d < 4; d++) {
for (int i = 0; i < h; i++)
Arrays.fill(visited[d][i], INF);
}
// 시작지점 처리
pq.add(from);
// bfs
while(!pq.isEmpty()){
Pos cur = pq.poll();
// 도착지점 도달
if(cur.x == to.x && cur.y == to.y)
return cur.mirrorCnt;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 범위를 벗어나거나 벽이면 넘어감
if(!inBound(nx, ny, w, h) || map[nx][ny] == '*') continue;
Pos next = new Pos(nx, ny, cur.mirrorCnt, d);
if(d != cur.dir) next.mirrorCnt++;
if(visited[d][nx][ny] > next.mirrorCnt) {
visited[d][nx][ny] = next.mirrorCnt;
pq.add(next);
}
}
}
return -1;
}
private static boolean inBound(int x, int y, int w, int h) {
return !(x < 0 || y < 0 || x >= h || y >= w);
}
}'Algorithm' 카테고리의 다른 글
| [백준] 1991: 트리 순회 JAVA (0) | 2023.02.15 |
|---|---|
| [백준] 11725: 트리의 부모 찾기 JAVA (0) | 2023.02.15 |
| [백준] 14938: 서강그라운드 JAVA (0) | 2023.02.07 |
| [백준] 1916: 최소비용 구하기 JAVA, C++ (0) | 2023.02.06 |
| [백준] 1446: 지름길 JAVA (0) | 2023.02.03 |
