[BFS] 백준 16920번 확장 게임 - JAVA

 

 

BFS 등 알고리즘 공식에 빠져 순수 while for 등 반복문을 활용하는 능력이 떨어진 것 같다.

그냥 구현력이 많이 떨어진다고 느꼈던 이번 문제였다 ㅠㅠ

그래서 다시 기록하며 공부!

 

---

1. 출처

---

 

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

16920번: 확장 게임

 

 

 

---

2. 설계

---

 

 

문제가 헷갈린다. 확실히 짚고가자면, "각 플레이어마다 갈 수 있는 N칸을 가는 길도 성을 세울 수 있다"

각 플레이어의 턴마다 지을 수 있는 성을 체크하려면 DFS를 생각할 수 있겠지만 시스템 콜을 쓰기 때문에 BFS보다 시간 효율이 좋지 않다. 때문에 BFS를 사용해야겠다고 생각했다.

 

1. 예제 입력 시 해야할 것들

- 각 맴버별 큐를 생성한다. -> static Queue<Loc>[] q;

- 지도를 입력할 때 1~9의 숫자가 나오면 맴버별 큐에 위치를 저장한다. 큐의 위치는 class Loc을 만들어 넣을 것이다.

- castle 어레이 변수에 각 맴버별 이동 위치를 저장한다.

 

 

2. BFS 함수를 만든다.

- 무한 루프(while) 안에서 다음 아래와 같은 행위를 반복한다.

    ㄴ각 유저마다 한 번씩 루프를 돈다.

    ㄴ1칸씩 움직일 것이기 때문에 각 플레이어마다 움직일 수 있는 거리만큼 루프를 돌려야한다.

    ㄴ큐에 저장된 모든 위치를 4방으로 1칸씩 움직일 것이다.

        ㄴ근데 빈칸('.')이면 플레이어의 큐에 또 넣는다. 성 갯수도 올린다.

    - 해당 플레이어의 큐가 모두 비었다면 다음 플레이어로 넘어간다. -> 시간을 비약적으로 줄이는 한줄 코드

    - 모든 플레이어의 큐가 비었다면 무한루프를 종료한다. 즉 하나라도 플레이어들의 큐에 뭐가 있다면 무한루프를 종료하는 것이다.

 

눈치챘겠지만 파란색으로 표시된 부분은 모두 for문으로 작성했다. 즉 4중 for을 썼다...

빨간색으로 표시된 부분은 안넣었더니 1%밖에 퍼센트가 오르지 않았다. break 해주지 않으면 큐가 비어도 움직일 수 있는 거리만큼 계속 돌기 때문에 헛된 코드와 시간이 도는 것 같다.

 

 

3. 결과를 출력한다.

 

 

 

---

3. 전체 코드

---

 

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

class Main {
    
    static int N;
    static int M;
    static int P;
    static Queue<Loc>[] q;
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    static int[] move;
    static int[] castle;
    static char[][] map;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String NMP = br.readLine();
        StringTokenizer st = new StringTokenizer(NMP, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        String moves = br.readLine();
        st = new StringTokenizer(moves," ");

        q = new LinkedList[P+1];
        move = new int[P+1];//1부터 시작
        for(int i=1;i<=P;i++){
            move[i] = Integer.parseInt(st.nextToken());
            q[i] = new LinkedList<>();
        }

        map = new char[N][M];
        castle = new int[P+1];
        for(int i=0;i<N;i++){
            String line = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = line.charAt(j);
                if(map[i][j]-'0'>=1 && map[i][j]-'0'<=9){
                    q[map[i][j]-'0'].offer(new Loc(i, j));
                    castle[map[i][j]-'0']++;
                }
            }
        }

        BFS();

        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=P;i++){
            sb.append(castle[i]).append(" ");
        }

        System.out.println(sb);
        
    }

    public static void BFS(){
        
        while(true){
            for(int p=1;p<=P;p++){//지금 누구?
                for(int time=1;time<=move[p];time++){//몇 칸 이동?
                    int size = q[p].size();
                    for(int i=0;i<size;i++){//현재 사람이 가진 성 갯수
                        Loc cur = q[p].poll();
                        for(int d=0;d<4;d++){//4방 탐색
                            int nextX = cur.x+drc[d][0];
                            int nextY = cur.y+drc[d][1];
                            if(nextX<0 || nextX>=N || nextY<0 || nextY>=M) continue;
                            if(map[nextX][nextY]=='.'){
                                q[p].offer(new Loc(nextX, nextY));
                                map[nextX][nextY] = map[cur.x][cur.y];
                                castle[map[nextX][nextY]-'0']++;
                            }
                        }// for d
                    }// for size
                    if(q[p].isEmpty()) break;
                }// for time
            }// for p

            //모든 q가 비어있으면 종료
            boolean flag = false;
            for(int p=1;p<=P;p++){
                if(q[p].size()>0) {
                    flag=true; //즉 하나라도 큐에 뭐가 있으면 돌아가
                    break;
                }
            }
            if(!flag) break;
        }//while true
    }
    

    public static class Loc{
        int x;
        int y;
        public Loc(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
}