문제 풀이

두개의 C중 하나를 시작지점으로 두고 BFS를 진행한다. 큐에는 좌표, 레이더 개수, 방향을 넣어둔다. BFS를 진행하면서 만약 가야하는 방향이 현재 저장되어있는 방향과 다르다면 꺾는다는 뜻이므로 거울을 하나 늘리는것이다. 그러므로 다음 큐에 삽입할때는 레이더 개수를 하나 늘려주고 아니면 그대로 가져간다.
여기서 visit배열에는 해당좌표에 들어갈 레이더의 최소 개수를 저장해둘것인데, 설정한 레이더 개수가 저장된 값보다 같거나 작으면 더 탐색해볼 가치가 있으므로 큐에 삽입해준다.
그렇게 해서 마지막에 또 다른 C의 좌표에 저장되어있는 레이더 개수를 출력해주면된다.

문제 링크

boj/6087

소스코드

PS/6087.java

import java.awt.List;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;


public class Main {
    static class Pair
    {
       public int x,y;

        public Pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }

    static class Ele
    {
       public int x,y,cnt,dir;

        public Ele(int x,int y,int cnt,int dir)
        {
            this.x=x;
            this.y=y;
            this.cnt =cnt;
            this.dir=dir;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static char [][]arr= new char[101][101];
    static int [][]visit= new int[101][101];
    static int []dx={0,1,0,-1};
    static int []dy= {1,0,-1,0};
    public static void main(String[] args) throws IOException {
      int w,h;
        StringTokenizer st = new StringTokenizer(br.readLine());
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        for(int i=0;i<h;i++)
            arr[i] = br.readLine().toCharArray();
        ArrayList<Pair> starts = new ArrayList<>();
        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++)
            {
                if(arr[i][j] =='C')
                    starts.add(new Pair(j, i));
                visit[i][j]=987654321;
            }
        }
       Queue<Ele> q =new LinkedList<>();
        q.add(new Ele(starts.get(0).x,starts.get(0).y,0,0));
        q.add(new Ele(starts.get(0).x,starts.get(0).y,0,1));
        q.add(new Ele(starts.get(0).x,starts.get(0).y,0,2));
        q.add(new Ele(starts.get(0).x,starts.get(0).y,0,3));
        visit[starts.get(0).y][starts.get(0).x] = 0;
        while(!q.isEmpty())
        {
            int x = q.peek().x;
            int y = q.peek().y;
            int cnt = q.peek().cnt;
            int dir = q.peek().dir;
            q.poll();
            for(int i=0;i<4;i++)
            {
                int nx =x+dx[i];
                int ny= y+dy[i];
                int next= cnt;
                if(nx>=0 && ny>=0 &&nx< w && ny< h && arr[ny][nx]!='*')
                {
                    if(dir != i)
                        next++;
                    if(visit[ny][nx]>= next) {
                        visit[ny][nx] =next;
                        q.add(new Ele(nx, ny, next, i));
                    }
                }
            }
        }
        bw.write(Integer.toString(visit[starts.get(1).y][starts.get(1).x]));
        bw.flush();
    }
}