[백준/BOJ] 2423번 전구를 켜라 자바 풀이

https://www.acmicpc.net/problem/2423

2423번: 전구를 켜라

 

문제

선영이는 N × M 직사각형 크기의 전자 회로를 디자인 하고 있다. 회로에는 N × M개의 정사각형 타일이 있고, 모두 직사각형의 변과 평행하다. 모든 타일은 두 개의 마주보는 꼭짓점이 전선으로 연결되어 있다. (그림 참조)

전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결되어 있다. 전구는  전원에서 전구로 가는 경로가 있을 때만 불이 켜진다. 전구에 불을 켜기 위해서, 선영이는 몇개의 타일을 90도 회전 시킬 수 있다.

 

위의 그림에서 전구는 꺼져있다. 만약 오른쪽에서 2번째 열 중 아무 칸이나 90도 회전시킨다면, 전원과 전구는 연결되어 전구가 켜지게 된다. 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 전자 회로의 상태가 주어진다. 상태는 / 또는 \이다. (1 ≤ N, M ≤ 500)

출력

첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다.

 

 

 

전형적인 다익스트라 또는 bfs 0-1 문제다.

조금은 지저분하게 푼 것 같아서.. 다음엔 bfs 0-1 방식으로 풀어봐야겠다.

 

 

전선이 하나로 연결되어 있는지 확인하기 위해서는, 현재 전선과 인접한 8개의 타일 모두를 확인하면 된다.

만약 현재 전선이 '\' 라면, 인접한 타일이 아래 표와 같이 구성되어야 연결된 것이다. (표에서 가장 가운데가 현재 전선)

\	/
/	\	/
	/	\

 

또한 현재 전선이 '/'라면, 인접한 타일이 아래 표와 같이 구성되어야 연결된 것이다.

	\	/
\	/	\
/	\

 

여기서 규칙을 찾을 수 있다.

대각선 -> 현재 전선과 다른 방향의 전선

상하좌우 -> 현재 전선과 같은 방향의 전선

이어야 연결된 것이다.

 

그리고 위 표에서 빈 부분은 어떤 방향으로도 연결될 수 없는 것이다.

 

 

	static void dijkstra() {
		PriorityQueue<Circuit> pq = new PriorityQueue<>((o1, o2) -> o1.cnt - o2.cnt);
		pq.offer(new Circuit(0, 0, 0, '\\'));
		visit[0][0] = 0;
		
		while(!pq.isEmpty()) {
			Circuit now = pq.poll();
			
			if(now.r == N - 1 && now.c == M - 1) {
				visit[N - 1][M - 1] = now.cnt;
				return;
			}
			
			for(int i=0;i<4;i++) { // 대각선으로 이동하는 경우, 현재 타일과 같아야 연결 가능
				if((now.wire == '\\' && (i == 1 || i == 2)) || (now.wire == '/' && (i == 0 || i == 3)))
					continue;
				
				int nextR = now.r + move1[i][0];
				int nextC = now.c + move1[i][1];
				
				if(!check(nextR, nextC))
					continue;
				
				if(now.wire == arr[nextR][nextC] && visit[nextR][nextC] > now.cnt) { // 연결되어 있으면
					visit[nextR][nextC] = now.cnt;
					pq.offer(new Circuit(nextR, nextC, now.cnt, now.wire));
				}
				else if(now.wire != arr[nextR][nextC] && visit[nextR][nextC] > now.cnt + 1
						&& (nextR != N - 1 || nextC != M - 1)) { // 연결되어 있지 않으면 타일 회전 (전구와 연결된 타일은 회전할 수 없음)
					visit[nextR][nextC] = now.cnt + 1; 
					pq.offer(new Circuit(nextR, nextC, now.cnt + 1, now.wire)); 
				}
			}
			
			for(int i=0;i<4;i++) { // 상하좌우로 이동하는 경우, 현재 타일과 달라야 연결 가능
				int nextR = now.r + move2[i][0];
				int nextC = now.c + move2[i][1];
				
				if(!check(nextR, nextC))
					continue;
				
				if(now.wire != arr[nextR][nextC] && visit[nextR][nextC] > now.cnt) { // 연결되어 있으면
					visit[nextR][nextC] = now.cnt;
					pq.offer(new Circuit(nextR, nextC, now.cnt, arr[nextR][nextC]));
				}
				else if(now.wire == arr[nextR][nextC] && visit[nextR][nextC] > now.cnt + 1
						&& (nextR != N - 1 || nextC != M - 1)) { // 연결되어 있지 않으면 타일 회전 (전구와 연결된 타일은 회전할 수 없음)
					visit[nextR][nextC] = now.cnt + 1; 
					pq.offer(new Circuit(nextR, nextC, now.cnt + 1, now.wire == '/' ? '\\' : '/')); 
				}
			}
		}
		
	}

즉, 다익스트라로 상하좌우, 대각선을 이동하면서 연결되어 있다면 visit를 갱신한다. (visit에는 타일을 돌리는 횟수가 저장)

연결되어 있지 않다면 그 타일을 돌린 후 visit를 갱신한다.

visit를 갱신할 때, 이미 visit에 더 작은 값이 저장되어 있다면 이미 타일을 돌리는 횟수가 더 최소인 경로로 탐색한 것이므로 갱신하지 않는다.

 

타일을 돌리는 횟수가 최소여야 하므로, 우선 순위 큐에 타일 횟수를 오름차순으로 넣고 차례로 꺼낸다.

전구에 인접한 전선(N-1, M-1)까지 도달한 경우 visit[N - 1][M - 1]에 현재 타일 회전 횟수를 넣고 메소드를 빠져나온다.

그리고 visit[N - 1][M - 1]를 출력하면 최소 타일 횟수가 된다.

만약 visit[N - 1][M - 1]이 INF라면 한번도 전선에 도달하지 못한 것, 즉 연결될 수 없는 것이므로 "NO SOLUTION"를 출력한다.

 

 

		int cnt = arr[N - 1][M - 1] == '\\' ? 0 : 1;
		cnt += arr[0][0] == '\\' ? 0 : 1;
		arr[N - 1][M - 1] = '\\';
		
		dijkstra();
		System.out.println(visit[N - 1][M - 1] == INF ? "NO SOLUTION" : (visit[N - 1][M - 1] + cnt));

또한 전구가 연결되기 위해서는 전원의 위치(arr[0][0]), 전구의 위치(arr[N-1][M-1])가 무조건 \이어야 한다.

만약 입력받은 배열에서 전원/전구의 위치가 /라면 \로 변경하고,

다익스트라를 수행한 후 값을 출력할 때 변경한 횟수를 더해준다.

 

				else if(now.wire == arr[nextR][nextC] && visit[nextR][nextC] > now.cnt + 1
						&& (nextR != N - 1 || nextC != M - 1)) { // 연결되어 있지 않으면 타일 회전 (전구와 연결된 타일은 회전할 수 없음)
					visit[nextR][nextC] = now.cnt + 1; 
					pq.offer(new Circuit(nextR, nextC, now.cnt + 1, now.wire == '/' ? '\\' : '/')); 
				}

전구의 위치는 \에서 /로 회전될 수 없으므로,

연결이 되어있지 않은 경우 if문에서 전구의 위치가 아닌 경우에만 회전할 수 있도록 한다.

 

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
	static int[][] move1 = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; // 대각선
	static int[][] move2 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
	static int N, M;
	static char[][] arr;
	static int[][] visit;
	static int INF = 987654321;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new char[N][M];
		visit = new int[N][M];
		
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				arr[i][j] = str.charAt(j);
				visit[i][j] = INF;
			}
		}
		
		int cnt = arr[N - 1][M - 1] == '\\' ? 0 : 1;
		cnt += arr[0][0] == '\\' ? 0 : 1;
		arr[N - 1][M - 1] = '\\';
		
		dijkstra();
		System.out.println(visit[N - 1][M - 1] == INF ? "NO SOLUTION" : (visit[N - 1][M - 1] + cnt));
	}
	
	static void dijkstra() {
		PriorityQueue<Circuit> pq = new PriorityQueue<>((o1, o2) -> o1.cnt - o2.cnt);
		pq.offer(new Circuit(0, 0, 0, '\\'));
		visit[0][0] = 0;
		
		while(!pq.isEmpty()) {
			Circuit now = pq.poll();
			
			if(now.r == N - 1 && now.c == M - 1) {
				visit[N - 1][M - 1] = now.cnt;
				return;
			}
			
			for(int i=0;i<4;i++) { // 대각선으로 이동하는 경우, 현재 타일과 같아야 연결 가능
				if((now.wire == '\\' && (i == 1 || i == 2)) || (now.wire == '/' && (i == 0 || i == 3)))
					continue;
				
				int nextR = now.r + move1[i][0];
				int nextC = now.c + move1[i][1];
				
				if(!check(nextR, nextC))
					continue;
				
				if(now.wire == arr[nextR][nextC] && visit[nextR][nextC] > now.cnt) { // 연결되어 있으면
					visit[nextR][nextC] = now.cnt;
					pq.offer(new Circuit(nextR, nextC, now.cnt, now.wire));
				}
				else if(now.wire != arr[nextR][nextC] && visit[nextR][nextC] > now.cnt + 1
						&& (nextR != N - 1 || nextC != M - 1)) { // 연결되어 있지 않으면 타일 회전 (전구와 연결된 타일은 회전할 수 없음)
					visit[nextR][nextC] = now.cnt + 1; 
					pq.offer(new Circuit(nextR, nextC, now.cnt + 1, now.wire)); 
				}
			}
			
			for(int i=0;i<4;i++) { // 상하좌우로 이동하는 경우, 현재 타일과 달라야 연결 가능
				int nextR = now.r + move2[i][0];
				int nextC = now.c + move2[i][1];
				
				if(!check(nextR, nextC))
					continue;
				
				if(now.wire != arr[nextR][nextC] && visit[nextR][nextC] > now.cnt) { // 연결되어 있으면
					visit[nextR][nextC] = now.cnt;
					pq.offer(new Circuit(nextR, nextC, now.cnt, arr[nextR][nextC]));
				}
				else if(now.wire == arr[nextR][nextC] && visit[nextR][nextC] > now.cnt + 1
						&& (nextR != N - 1 || nextC != M - 1)) { // 연결되어 있지 않으면 타일 회전 (전구와 연결된 타일은 회전할 수 없음)
					visit[nextR][nextC] = now.cnt + 1; 
					pq.offer(new Circuit(nextR, nextC, now.cnt + 1, now.wire == '/' ? '\\' : '/')); 
				}
			}
		}
		
	}
	
	static boolean check(int r, int c) {
		return (r < 0 || r >= N || c < 0 || c >= M) ? false : true;
	}

	static class Circuit {
		int r, c, cnt;
		char wire;
		
		Circuit(int r, int c, int cnt, char wire) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.wire = wire;
		}
	}
}