6078 레이저 통신

오늘은 날씨가 우중충하니 좋네요. 비도오고 좋네요. 저는 비오는걸 좋아합니다. 물론 비맞는거 말고 비오는 걸 보는걸 좋아합니다. 아무튼 이번문제는 

 

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

6087번: 레이저 통신

 

문제는 자체는 크게 어려운 부분이 없었는데, 디버깅이랑 여러 케이스에 만족하게 하는 디테일을 생각하는게 어려웠습니다. 백준의 타노스를 만나서...

 

 

-나의 풀이- 

 

문제는 크게 막 어려운 부분은 없었습니다. 아마 탈옥과 백조한테 뚜까 맞으며 길러진 저의 프로그래밍 실력 덕분이겠죠? 레이저가 서로 이어질수 있게 최소 거울의 갯수를 구해야합니다. 또 최소 어쩌구를 구하는 문제이군요.

역시나 최소인 상황을 구하기 위해서는 모든 경우를 다 탐색하여야합니다. 

 

모든 경우를 한번의 BFS안에 탐색을 하는 방법을 생각해보았습니다. (입력값의 범위가 10^2 이긴하지만)

 

제가 레이저가 되어 지도를 누비는 방법을 생각하다가 관뒀습니다. 프로그래밍에서 뒤로가기를 구현하는 건 귀찮은 과정이라 생각이 들었기 때문입니다. 

 

 어느한 지점에 최소 몇개의 거울이 있어야 도달할 수 있는지를 구하면 좋을 것 같다는 생각이 들었습니다. 

그렇게 구하면 우선 방문여부를 거울의 갯수를 보고 판단할 수 있으니까요. 

 

구현하기 전, 어떻게 구현할지에 대해 생각해보았습니다.

 

1. 레이저는 한방향으로 쭈욱간다. 

> DFS로 구현하면 편하겠지만..BFS로 구현해야하는 경우 PriorityQueue로 구현하면 가능합니다. 

> PriorityQue를 사용하기 위해서는 객체 (Laser)에 '현재사용 거울 갯수'를 저장하는게 좋아보입니다.

 

2. 레이저는 90도로 꺾인다.

> 어 4방향에서 2방향으로 줄었으니까 개꿀~이라고 생각할 수 있지만, 현재 이동방향에 따라서 다르게 방향을 전환하여야 하기때문에 아닙니다.ㅠ

> 때문에 객체(Laser)에 방향정보 또한 저장해줘야합니다. 

 

3. 방문처리는 거울의 갯수를 이용하자!

> 이미 방문했더라도 현재 진행중인 레이저의 거울의 갯수가 같거나 적으면 다시 방문해서 그 값을 저장해준다.

 

요정도만 생각하고 구현했더니..

우와..!

제가 놓친 부분은

1. Buffer로 입력받을 때, C의 위치를 저장하는 방법에서..

public class Main {
	static int w,h;
	static char[][] map;
	static int[] dx = {1,-1,0,0} , dy = {0,0,1,-1};
	static List<Laser> coreLocation = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = bf.readLine().split(" ");
		w = Integer.parseInt(tmp[0]);
		h = Integer.parseInt(tmp[1]);
		map = new char[h][w];
		for(int i=0;i <h; i++) {
			String input = bf.readLine();
			map[i] = input.toCharArray();
			if(input.contains("C")) { // ....CC..이면 하나의 C만 저장
				coreLocation.add(new Laser(i,input.indexOf('C'),0,0));
			}
		}
		System.out.println(BFS());

	}

이런식이면 한줄에 C가 두개 있으면 혼납니다. (Scanner가 그리읍다..)

 

2. 방문처리를 거울의 갯수로만 특수한 상황에서 처리할 경우 메모리와 시간에서 불이익을 본다

이를 설명하기 위해..

눈으로 보는게 최고긴해

이렇게 하나의 진행중인 레이저가 다음점으로 갈 수 있을때, 큐에 3개씩 넣어줍니다. 

근데 만약 이 점을 재방문 했을때도, 큐에 3개를 넣어줘야 할까요? (급 질문)

재방문했을때는 현재 진행되는 레이저의 거울 수와 목표하는 지점의 거울갯수가 같은 경우입니다. (작은경우는 우선 제머리로는 존재하지않다고 생각되는데..)

즉, 이미 방문을 헀었다면 구지 큐에 3개를 넣어줄 필요가 없습니다. 3번 레이저 현재 방향과 같은 레이저만 넣어주면 되죠.

만일 테스트 케이스가 이런 경우에는 큐에 너무 많이 넣어서 메모리초과가 나옵니다.

input:
100 7
...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*
C*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*.*
...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*
**************************************************************************************************.*
...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*
C*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*.*
...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*

output:
196

<출처: 백준아이디 djm03178님 이 케이스 추가로 통계 정답케이스 절반이 사라짐 >

 

저는 그래서 boolean[ ] [ ] 를 하나더 도입하여 구현헀는데, 지금와서 생각하니 초기 값과 비교만 해주면 되니 구지 없어도 될 것 같습니다. 

 

-코드-

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Laser implements Comparable<Laser>{
	int mirror;
	int direct;
	int w;
	int h;
	Laser(int h,int w,int mirror, int direct){
		this.direct = direct;
		this.mirror = mirror;
		this.w = w;
		this.h = h;
	}
	@Override
	public int compareTo(Laser oj) {
		return this.mirror - oj.mirror;
	}
	
}
public class Num6087 {
	static int w,h;
	static char[][] map;
	static int[] dx = {1,-1,0,0} , dy = {0,0,1,-1};
	static List<Laser> coreLocation = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = bf.readLine().split(" ");
		w = Integer.parseInt(tmp[0]);
		h = Integer.parseInt(tmp[1]);
		map = new char[h][w];
		for(int i=0;i <h; i++) {
			String input = bf.readLine();
			int j =0;
			for(char x:input.toCharArray()) {
				map[i][j] = x;
				if(x=='C') {
					coreLocation.add(new Laser(i,j,0,0));
				}
				j++;
			}
			
		}
		System.out.println(BFS());

	}
	public static int BFS() {
		PriorityQueue<Laser> pq = new PriorityQueue<>();
		boolean[][] vist = new boolean[h][w];
		int[][] answerSheet = new int[h][w];
		for(int i=0;i<h;i++) {
			Arrays.fill(answerSheet[i], 100000);
		}
		int startH = coreLocation.get(0).h;
		int startW = coreLocation.get(0).w;
		answerSheet[startH][startW] = 0;
		vist[startH][startW] = true;
		for(int i=0;i<4;i++) {
			pq.add(new Laser(startH,startW,0,i));
		}
		while(!pq.isEmpty()) {
			Laser nowL = pq.poll();
			vist[nowL.h][nowL.w] = true;
			if(valid(nowL,answerSheet)) {
				pq.add(new Laser(nowL.h+dx[nowL.direct],nowL.w+dy[nowL.direct],nowL.mirror,nowL.direct));
				if(!vist[nowL.h+dx[nowL.direct]][nowL.w+dy[nowL.direct]]) {
					if(nowL.direct<2) {
						pq.add(new Laser(nowL.h+dx[nowL.direct],nowL.w+dy[nowL.direct],nowL.mirror+1,2));
						pq.add(new Laser(nowL.h+dx[nowL.direct],nowL.w+dy[nowL.direct],nowL.mirror+1,3));
					}else {
						pq.add(new Laser(nowL.h+dx[nowL.direct],nowL.w+dy[nowL.direct],nowL.mirror+1,0));
						pq.add(new Laser(nowL.h+dx[nowL.direct],nowL.w+dy[nowL.direct],nowL.mirror+1,1));
					}	
				}
			}
		
		}
		return answerSheet[coreLocation.get(1).h][coreLocation.get(1).w];
	}
	public static boolean valid(Laser L,int[][] answerSheet) {
		if(L.h+dx[L.direct]>=0 && L.h+dx[L.direct]<h && 
				L.w+dy[L.direct]>=0 && L.w+dy[L.direct]<w &&
				answerSheet[L.h+dx[L.direct]][L.w+dy[L.direct]] >=L.mirror &&
				map[L.h+dx[L.direct]][L.w+dy[L.direct]]!='*') {
			answerSheet[L.h+dx[L.direct]][L.w+dy[L.direct]] = Math.min(L.mirror,answerSheet[L.h+dx[L.direct]][L.w+dy[L.direct]]);
			return true;
		}
		return false;
	}

}

 

-후 기-

 

1. 버퍼로 입력받을때 조심하자

2. 역시 디버깅이 더 어렵다

3. 그래도 오늘은 만족 ;)