[백준] 12180 - Googlander (Java)

문제 파악

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

어쩌다 영어 문제를 풀게 되었다..

풀이

본문에 따르자면 "우아한" 경로의 수를 출력한다.

우아한 경로를 만들기 위한 조건은 다음과 같다.
진행 방향을 그대로 유지하는 방법, 진행 방향에서 오른쪽으로 90도 회전하여 진행하는 방법이다.

만일 위 두 가지 경로가 이미 방문한 경로이거나, 범위를 벗어난 경우 그 자리에서 멈추고 종료한다.

보통은 시작점과 끝점이 동일한 문제가 많이 주어졌으나, 해당 문제는 우아한 경로를 만들지 않는 경우에는 종료하는 형태를 띄어 진행할 때마다 방문 정보를 가지고 있어야 한다.

문제에서 주어지는 행/열의 범위는 10으로 적은 편에 속하며, 직진/우회전이라는 2가지 경우의 수를 갖고 있기에 재귀를 선택하여 풀이했다.

물론 스택을 이용하여 풀이할 수도 있다. 두가지 풀이 모두 첨부하였다.

간단한 팁💡

• 문제는 (r-1, 0) 지점에 위쪽 방향으로 시작하는 데 반해,
  나는 풀이를 쉽게 하기 위해 (0,0) 지점에서 우측 방향으로 시작하도록 구현하였다.
• 진행 방향은 북, 동, 남, 서 로 지정해 현재 방향의 다음 방향이 90도 회전한 방향일 수 있도록 선언하였다.

코드

재귀

import java.io.*;

public class Main {
    public static final String CASE_WRITER = "Case #%d: %d";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = Integer.parseInt(br.readLine());
        for (int i = 1; i <= count; i++) {
            try {
                String[] input = br.readLine().split(" ");
                int r = Integer.parseInt(input[0]);
                int c = Integer.parseInt(input[1]);
                bw.append(String.format(CASE_WRITER, i, backtracking(0, 0, r, c, 1, new boolean[r * c])))
                        .append("\n");
            } catch (Exception e) {
                break;
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }

    // 상, 우, 하, 좌
    static final int[][] DIR = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static int backtracking(int r, int c, int totalR, int totalC, int dir, boolean[] visit) {
        if (r < 0 || r >= totalR || c < 0 || c >= totalC || visit[r * totalC + c]) {
            return 0;
        }
        visit[r * totalC + c] = true;
        int value = 0;
        int nextR = r + DIR[dir][0];
        int nextC = c + DIR[dir][1];
        value += backtracking(nextR, nextC, totalR, totalC, dir, visit);

        int newDir = (dir + 1) % 4;
        nextR = r + DIR[newDir][0];
        nextC = c + DIR[newDir][1];
        value += backtracking(nextR, nextC, totalR, totalC, newDir, visit);
        visit[r * totalC + c] = false;
        return Math.max(value, 1);
    }
}

스택

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

public class Main {
    public static final String CASE_WRITER = "Case #%d: %d";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = Integer.parseInt(br.readLine());
        for (int i = 1; i <= count; i++) {
            try {
                String[] input = br.readLine().split(" ");
                int r = Integer.parseInt(input[0]);
                int c = Integer.parseInt(input[1]);
                bw.append(String.format(CASE_WRITER, i, solution(r, c)))
                        .append("\n");
            } catch (Exception e) {
                break;
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }

    // 상, 우, 하, 좌
    static final int[][] DIR = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static int solution(int r, int c) {
        int answer = 0;
        Stack<Node> stack = new Stack<>();
        boolean[] v = new boolean[r * c];
        stack.push(new Node(0, 0, 1, v));
        while (!stack.isEmpty()) {
            Node latest = stack.pop();
            boolean[] visit = latest.visit;
            visit[latest.r * c + latest.c] = true;
            int sR = latest.r + DIR[latest.dir][0];
            int sC = latest.c + DIR[latest.dir][1];

            int rD = (latest.dir + 1) % 4;
            int rR = latest.r + DIR[rD][0];
            int rC = latest.c + DIR[rD][1];

            if ((!isInRange(rR, rC, r, c)|| visit[rR * c + rC])
                    && (!isInRange(sR, sC, r, c)|| visit[sR * c + sC]))  {
                // 우아한 경로가 생성되지 않을 경우, 종료한다
                answer++;
                continue;
            }
            if (isInRange(sR, sC, r, c) && !visit[sR * c + sC]) {
                stack.push(new Node(sR, sC, latest.dir, visit.clone()));
            }
            if (isInRange(rR, rC, r, c) && !visit[rR * c + rC]) {
                stack.push(new Node(rR, rC, rD, visit.clone()));
            }
        }
        return answer;
    }

    static boolean isInRange(int r, int c, int totalR, int totalC) {
        return r >= 0 && r < totalR && c >= 0 && c < totalC;
    }

    static class Node {
        int r;
        int c;
        int dir;
        boolean[] visit;

        public Node(int r, int c, int dir, boolean[] visit) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.visit = visit;
        }
    }
}