백준 - 6087 레이저 통신

www.acmicpc.net/problem/6087

6087번: 레이저 통신

1. 유형

bfs, dp, 구현

 

2. 자료구조

큐

 

3. 풀이

이 문제는 거울->몇번 꺾이는가 로 해석해야 합니다.

 

이 문제의 핵심은 bfs입니다. 하지만 일반적인 문제와 다르게 최단 거리가 아닌,

 

경로가 더 길더라도 더 적게 꺾이는 경로를 찾는게 핵심입니다.

 

처음 생각은 우선순위큐와 3차원 배열을 사용 입니다.

 

하지만, 메모리초과가 나와서 실패했습니다.

 

두번째는 메모리제이션을 사용하는것 입니다. 이부분을 생각하지 못해서 많은 시간을 썼습니다.

 

visited배열을 int형식으로 선언하고, max값으로 초기화합니다.

 

그리고 다음 좌표를 갈때, 방문한 값이면 더 적게 꺾은 상태만 이동할 수 있습니다.

 

 

클래스는 좌표, 방향, 꺽은 횟수를 저장합니다.

 

4. 디버깅

처음에는 일반적인 bfs를 사용했습니다. -> 최단경로+꺾은 횟수를 구함.

 

우선순위큐를 사용 -> 꺾은 횟수가 작은거 먼저 탐색 -> 하지만 메모리초과

 

DP사용 -> 완벽해결

 

코테에 dp문제가 그렇게 많이 나오는게 아니라 별로 풀지 않았는데

이제는 조금씩 풀어봐야 할거 같습니다.

 

5. 코드

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

public class Main {
	static int N, M;
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static char map[][];
	static int sr, sc, answer;
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };

	static class Node{
		int r, c, d, cnt;

		Node(int r, int c, int d, int cnt) {
			this.r = r;
			this.c = c;
			this.d = d;
			this.cnt = cnt;
		}
	}

	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		int visited[][] = new int[N][M];
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				visited[i][j] = Integer.MAX_VALUE;
			}
		}
		q.add(new Node(sr, sc, 4, 0));
		visited[sr][sc] = 0;
		while (!q.isEmpty()) {
			Node cur = q.poll();
			if(map[cur.r][cur.c] == 'C') {
				answer = Math.min(answer, cur.cnt);
				continue;
			}
			for (int k = 0; k < 4; k++) {
				int nr = cur.r + dr[k];
				int nc = cur.c + dc[k];
				if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc]=='*')
					continue;
				if (k != cur.d) {
					if(visited[nr][nc] >= cur.cnt+1) {
						visited[nr][nc] = cur.cnt+1;
						q.add(new Node(nr, nc, k, cur.cnt + 1));
					}
				}else {
					if(visited[nr][nc] >= cur.cnt) {
						visited[nr][nc] = cur.cnt;
						q.add(new Node(nr, nc, k, cur.cnt));
					}
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(in.readLine());
		M = Integer.valueOf(st.nextToken());
		N = Integer.valueOf(st.nextToken());
		map = new char[N][M];
		boolean flag = false;
		for (int i = 0; i < N; i++) {
			String str = in.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == 'C' && !flag) {
					flag = true;
					sr = i;
					sc = j;
					map[i][j] = 'S';
				}
			}
		}
		answer = Integer.MAX_VALUE;
		bfs();
		System.out.println(answer-1);
	}
}