[백준] 23747: 와드 - JAVA

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

 

풀이

이 문제는 보드 위에서 이동과 와드 설치를 처리하는 문제로, 주어진 명령에 따라 보드의 상태를 변화시켜야 한다.

 

W 명령을 수행하여 해당 위치와 인접한 같은 타입의 영역을 방문 처리하고, 상하좌우 이동을 통해 요리사의 위치를 업데이트했다.

 

최종적으로 방문한 위치를 '.'으로 표시하고, 방문하지 않은 위치를 '#'으로 표시하여 결과를 출력했다.

 

---

 

메모리: 127596KB
시간: 720ms
언어: Java 11

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

public class Main {
    static int r, c;
    static char[][] board;
    static boolean[][] result;
    static String moves;

    static int[][] vector = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        board = new char[r][c];
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        st = new StringTokenizer(br.readLine());
        int Hr = Integer.parseInt(st.nextToken()) - 1;
        int Hc = Integer.parseInt(st.nextToken()) - 1;
        moves = br.readLine();

        result = new boolean[r][c];
        moving(Hr, Hc, 0);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                sb.append(result[i][j] ? '.' : '#');
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static void moving(int hr, int hc, int idx) {
        if (idx == moves.length()) {
            for (int k = 0; k < 4; k++) {
                int nr = hr + vector[k][0];
                int nc = hc + vector[k][1];

                if (nr < 0 || nc < 0 || nr >= r || nc >= c) {
                    continue;
                }

                result[nr][nc] = true;
            }
            result[hr][hc] = true;
            return;
        }

        char move = moves.charAt(idx);
        switch (move) {
            case 'W':
                putWard(hr, hc);
                moving(hr, hc, idx + 1);
                break;

            case 'U':
                moving(hr - 1, hc, idx + 1);
                break;

            case 'D':
                moving(hr + 1, hc, idx + 1);
                break;

            case 'L':
                moving(hr, hc - 1, idx + 1);
                break;

            case 'R':
                moving(hr, hc + 1, idx + 1);
                break;
        }
    }

    private static void putWard(int hr, int hc) {
        char type = board[hr][hc];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { hr, hc });

        result[hr][hc] = true;

        while (!queue.isEmpty()) {
            int[] node = queue.poll();

            for (int k = 0; k < 4; k++) {
                int nr = node[0] + vector[k][0];
                int nc = node[1] + vector[k][1];

                if (nr < 0 || nc < 0 || nr >= r || nc >= c) {
                    continue;
                }

                if (result[nr][nc] || board[nr][nc] != type) {
                    continue;
                }

                result[nr][nc] = true;
                queue.add(new int[] { nr, nc });
            }
        }
    }

}