[백준 6087] 레이저 통신(Java)

1. 문제

www.acmicpc.net/problem/6087

6087번: 레이저 통신

2. 풀이

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

		public Node(int r, int c, int d, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
			this.cnt = cnt;
		}
	}
	
	static int n,m;
	static char[][]map;
	static int[][]visited;
	static Queue<Node>que;
	static int [][]dir = {{-1,0},{0,1},{1,0},{0,-1}};
	static ArrayList<Node>list;
	static int result = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//	br = new BufferedReader(new StringReader(src));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        visited = new int[n][m];
        list = new ArrayList<>();
        for(int i =0; i<n; i++) {
        	String str = br.readLine();
        	for(int j =0; j<m;j++) {
        		map[i][j] = str.charAt(j);
        		visited[i][j] = Integer.MAX_VALUE;
        		if(map[i][j] =='C') {
        			list.add(new Node(i, j, -1, 0));
        		}
        	}
        }
      
        bfs();
        System.out.println(result);
       
	}
	static void bfs() {
		
		Node start = list.get(0);
		Node end = list.get(1);
		
		que = new LinkedList<>();
		que.offer(start);
		visited[start.r][start.c]=0;
		while(!que.isEmpty()) {
			
			Node top = que.poll();
			
			
			if(top.r == end.r && top.c == end.c) {
				result = Math.min(result, top.cnt);
//				break;
			}

			
			for(int d=0; d<4; d++) {
				int newR = top.r+dir[d][0];
				int newC = top.c+dir[d][1];
				
				if(isRange(newR, newC) && map[newR][newC]!='*') {
					int tmp=top.cnt;
					if(top.d !=d && top.d!=-1) {
						tmp++;
					}
					if(visited[newR][newC]<tmp) continue;
					visited[newR][newC]= tmp;
					que.offer(new Node(newR, newC, d, tmp));
				}
			}
			
		}
	}
	static boolean isRange(int r, int c) {
		return r>=0 && c>=0 && n>r && m>c;
	}
	static String src="7 8\r\n" + 
			".......\r\n" + 
			"......C\r\n" + 
			"......*\r\n" + 
			"*****.*\r\n" + 
			"....*..\r\n" + 
			"....*..\r\n" + 
			".C..*..\r\n" + 
			".......";
}

반응형