import java.io.*;
import java.util.*;
class Main{
static int[] di = {1,-1,0,0};//아래 위 우 좌
static int[] dj = {0,0,1,-1};
static int N,startI,startJ,targetI,targetJ;
static char[][] map;
static int[][][] visited;
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visited = new int[N][N][4];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
Arrays.fill(visited[i][j],Integer.MAX_VALUE);
}
}
map = new char[N][N];
boolean flag = true;
for(int i=0;i<N;i++){
String s = br.readLine();
for(int j=0;j<N;j++){
map[i][j] = s.charAt(j);
if(map[i][j] == '#'){
if(flag){
startI = i;
startJ = j;
flag = false;
}else{
targetI = i;
targetJ = j;
}
}
}
}
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(startI, startJ,0,0));
visited[startI][startJ][0] = 0;
q.add(new Node(startI, startJ,1,0));
visited[startI][startJ][1] = 0;
q.add(new Node(startI, startJ,2,0));
visited[startI][startJ][2] = 0;
q.add(new Node(startI, startJ,3,0));
visited[startI][startJ][3] = 0;
while(!q.isEmpty()){
Node node = q.poll();
if(node.i == targetI && node.j == targetJ){
ans = Math.min(ans, node.mirrorCnt);
continue;
}
//아... 관성적으로 for 4 이거했는데 아니지.. 빛이잖어...
int ni = node.i + di[node.dir];
int nj = node.j + dj[node.dir];
if(ni<0 || ni >= N || nj<0 || nj >=N) continue;
if(map[ni][nj] == '*') continue;
//if(visited[ni][nj][node.dir] != -1 && visited[ni][nj][node.dir] > node.mirrorCnt) continue;
//!일때(꺽)
if(map[ni][nj] == '!'){
if(node.dir == 0 || node.dir == 1){
if(visited[ni][nj][2]>node.mirrorCnt+1){
q.add(new Node(ni,nj,2,node.mirrorCnt+1));
visited[ni][nj][2] = node.mirrorCnt+1;
}
if(visited[ni][nj][3]>node.mirrorCnt+1){
q.add(new Node(ni,nj,3,node.mirrorCnt+1));
visited[ni][nj][3] = node.mirrorCnt+1;
}
}else {
if(visited[ni][nj][0]>node.mirrorCnt+1){
q.add(new Node(ni,nj,0,node.mirrorCnt+1));
visited[ni][nj][0] = node.mirrorCnt+1;
}
if(visited[ni][nj][1]>node.mirrorCnt+1){
q.add(new Node(ni,nj,1,node.mirrorCnt+1));
visited[ni][nj][1] = node.mirrorCnt+1;
}
}
}
//아닐때(그냥 방향 유지한다.) 아 이건 무조건 있어야되
if(visited[ni][nj][node.dir]>node.mirrorCnt){
q.add(new Node(ni,nj,node.dir,node.mirrorCnt));
visited[ni][nj][node.dir] = node.mirrorCnt;
}
}
System.out.print(ans);
}
static class Node{
int i,j,dir,mirrorCnt;
Node(int i, int j,int dir,int mirrorCnt){
this.i = i;
this.j = j;
this.dir = dir;
this.mirrorCnt = mirrorCnt;
}
}
}
안녕하세요! 작성하신 코드를 보니 거울 설치 문제를 BFS(너비 우선 탐색)를 이용해 풀려고 시도하신 점이 훌륭합니다. 상태를 (행, 열, 방향, 거울 개수)로 정의하고 3차원 visited 배열을 사용한 접근 방식은 매우 정확합니다.
하지만 코드의 핵심 로직, 특히 빛이 움직이는 방식을 처리하는 부분에 작은 오류가 있습니다. 이 부분을 수정하면 정답을 찾을 수 있습니다.
문제의 핵심
이 문제는 가중치가 다른 최단 경로 찾기 문제입니다.
- 직진: 비용(거울 개수)이 0만큼 증가합니다.
- 회전: 비용(거울 개수)이 1만큼 증가합니다.
이처럼 간선의 가중치가 0 또는 1인 경우에는 0-1 BFS나 다익스트라(Dijkstra) 알고리즘을 사용하는 것이 가장 효율적이고 정확합니다. ==일반적인 Queue를 사용하면, 거울을 많이 사용했지만 이동 거리가 짧은 경로를 먼저 탐색하게 되어 최소 거울 개수를 보장할 수 없습니다==.
틀린 부분 (원인 분석)
가장 큰 문제는 while 루프 안의 for 문입니다.
// 현재 코드의 잘못된 부분
for(int i=0; i<4;i++){ // <-- 이 부분이 문제입니다.
int ni = node.i + di[i];
int nj = node.j + dj[i];
// ...
}이 코드는 현재 위치 (node.i, node.j)에서 상하좌우 모든 방향으로 한 칸씩 이동하는 것을 시도합니다. 하지만 빛은 그렇게 움직이지 않습니다. 빛은 현재 진행하던 방향(node.dir)으로만 직진해야 합니다. 방향을 바꾸는 것은 거울을 만났을 때만 가능하며, 이는 비용(거울 개수)을 증가시키는 별개의 행동입니다.
해결 방법: 다익스트라 알고리즘 적용
PriorityQueue를 사용하여 다익스트라 알고리즘을 적용하면 이 문제를 간단하고 정확하게 해결할 수 있습니다. PriorityQueue는 거울을 가장 적게 사용한 Node를 항상 먼저 꺼내주기 때문에, 목표 지점에 처음 도달했을 때가 최소 거울 개수를 보장합니다.
아래는 수정한 전체 코드입니다.
수정된 전체 코드
import java.io.*;
import java.util.*;
class Main{
static int[] di = {1,-1,0,0};//아래(0) 위(1) 우(2) 좌(3)
static int[] dj = {0,0,1,-1};
static int N,startI,startJ,targetI,targetJ;
static char[][] map;
// visited[i][j][k]: (i, j)에 k 방향으로 도달했을 때의 최소 거울 개수
static int[][][] visited;
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visited = new int[N][N][4];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
Arrays.fill(visited[i][j],Integer.MAX_VALUE);
}
}
boolean flag = true;
for(int i=0;i<N;i++){
String s = br.readLine();
for(int j=0;j<N;j++){
map[i][j] = s.charAt(j);
if(map[i][j] == '#'){
if(flag){
startI = i;
startJ = j;
flag = false;
}else{
targetI = i;
targetJ = j;
}
}
}
}
// 우선순위 큐를 사용하여 다익스트라 알고리즘 구현
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작점에서 4방향으로 출발하는 경우를 모두 큐에 추가
// 시작점에서는 거울을 사용하지 않고 방향을 정할 수 있음
for (int i = 0; i < 4; i++) {
pq.add(new Node(startI, startJ, i, 0));
visited[startI][startJ][i] = 0;
}
while(!pq.isEmpty()){
Node node = pq.poll();
int r = node.i;
int c = node.j;
int dir = node.dir;
int mirrorCnt = node.mirrorCnt;
// 이미 더 적은 거울로 방문한 경우 스킵
if(visited[r][c][dir] < mirrorCnt) {
continue;
}
// 목표 지점에 도달하면 종료 (다익스트라이므로 최초 도달이 최단 경로)
if(r == targetI && c == targetJ){
ans = mirrorCnt;
break;
}
// 1. 현재 방향으로 직진 (비용: 0)
int ni = r + di[dir];
int nj = c + dj[dir];
if (ni >= 0 && ni < N && nj >= 0 && nj < N && map[ni][nj] != '*') {
if (visited[ni][nj][dir] > mirrorCnt) {
visited[ni][nj][dir] = mirrorCnt;
pq.add(new Node(ni, nj, dir, mirrorCnt));
}
}
// 2. 현재 위치에 거울 설치 후 90도 회전 (비용: 1)
// 거울은 '!' 또는 시작점('#')에서만 설치 가능
if(map[r][c] == '!') {
// 현재 방향이 수직(아래, 위)이었다면 수평(오른쪽, 왼쪽)으로 회전
if (dir < 2) {
for (int newDir = 2; newDir < 4; newDir++) {
int nni = r + di[newDir];
int nnj = c + dj[newDir];
if (nni >= 0 && nni < N && nnj >= 0 && nnj < N && map[nni][nnj] != '*') {
if (visited[nni][nnj][newDir] > mirrorCnt + 1) {
visited[nni][nnj][newDir] = mirrorCnt + 1;
pq.add(new Node(nni, nnj, newDir, mirrorCnt + 1));
}
}
}
}
// 현재 방향이 수평이었다면 수직으로 회전
else {
for (int newDir = 0; newDir < 2; newDir++) {
int nni = r + di[newDir];
int nnj = c + dj[newDir];
if (nni >= 0 && nni < N && nnj >= 0 && nnj < N && map[nni][nnj] != '*') {
if (visited[nni][nnj][newDir] > mirrorCnt + 1) {
visited[nni][nnj][newDir] = mirrorCnt + 1;
pq.add(new Node(nni, nnj, newDir, mirrorCnt + 1));
}
}
}
}
}
}
System.out.println(ans);
}
// Node 클래스가 Comparable을 구현하도록 수정
static class Node implements Comparable<Node> {
int i,j,dir,mirrorCnt;
Node(int i, int j,int dir,int mirrorCnt){
this.i = i;
this.j = j;
this.dir = dir;
this.mirrorCnt = mirrorCnt;
}
@Override
public int compareTo(Node o) {
// 거울 개수가 적은 것을 우선으로
return this.mirrorCnt - o.mirrorCnt;
}
}
}
주요 변경점 요약
PriorityQueue사용: 일반Queue대신PriorityQueue를 사용하여 거울 개수(mirrorCnt)가 가장 적은 노드를 우선적으로 탐색하도록 했습니다.Node클래스 수정:PriorityQueue에서 정렬 기준으로 사용하기 위해Comparable<Node>인터페이스를 구현하고compareTo메소드를 오버라이드했습니다.- 탐색 로직 수정:
- 잘못된
for(int i=0; i<4; i++)루프를 제거했습니다. - 대신 두 가지 행동으로 명확히 구분했습니다.
- 행동 1: 직진: 현재 방향(
node.dir)으로 한 칸 이동합니다. 이 때 거울 개수는 그대로입니다. - 행동 2: 회전: 현재 위치
(node.i, node.j)가'!'일 경우, 90도 꺾이는 두 방향으로 한 칸 이동하는 경우를 큐에 추가합니다. 이 때 거울 개수는+1이 됩니다.
- 행동 1: 직진: 현재 방향(
- 잘못된
- 시작점 처리: 시작점에서는 4방향 모두 거울 없이 출발할 수 있으므로, 4개의
Node를 초기에PriorityQueue에 넣어줍니다. (기존 코드의 이 부분은 좋았습니다.) - 종료 조건: 다익스트라 알고리즘의 특성상, 목표 지점에 처음 도달했을 때의
mirrorCnt가 최소값이므로, 바로break를 통해 탐색을 종료하고 효율성을 높였습니다.
이렇게 수정하면 빛의 움직임을 정확하게 시뮬레이션하여 최소 거울 개수를 찾을 수 있습니다.