SWEA 5650번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

문제

---

생각하기

---

• 부르트 포스 문제이다.
  • 모든 가능한 출발지에서 모든 방향의 탐색을 실행해서 가장 높은 점수를 구해야 함

• DFS이기는 하나 재귀를 사용하지 않고 무한반복을 사용해서 방향탐색을 실행했음

동작

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
 
                    // 돌아온다는 것을 감안했을 때, isVisited는 없어도 될 것 같음
                    if (map[i][j] == 0) {
                        for (int k = 0; k < 4; k++) {
                            DFS(i, j, i, j, k);
                        }
                    }
                }
            }

특별한 방법은 없고, 사실 상 방향에 대한 구현만 해주면 되는데 공이 어디서 시작해서 어떤 방향으로 갔을 때 가장 높은 점수를 얻을 수 있는지 알아야 하기 때문에 map[i][j]가 0일 경우, 4가지 방향으로 모두 돌려주면 된다.

이렇게 하면 완전탐색을 통해서 정답을 찾을 수 있다.

코드

---

Java

import java.util.*;
import java.io.*;
 
public class Solution {
    static int N, result;
    static int[][] map;
 
    static int[] dirX = {-1, 1, 0, 0}; // 상 하 좌 우
    static int[] dirY = {0, 0, -1, 1};
 
    static class Coordinates {
        int x;
        int y;
 
        public Coordinates(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } // End of Coordinates
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append('#').append(t).append(' ');
 
            N = Integer.parseInt(br.readLine());
            init();
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
 
                    // 돌아온다는 것을 감안했을 때, isVisited는 없어도 될 것 같음
                    if (map[i][j] == 0) {
                        for (int k = 0; k < 4; k++) {
                            DFS(i, j, i, j, k);
                        }
                    }
                }
            }
 
            sb.append(result).append('\n');
        }
 
        bw.write(sb.toString());
        bw.close();
    } // End of main
 
    private static void DFS(int startX, int startY, int x, int y, int direction) {
        int hitCount = 0;
        int nowX = x;
        int nowY = y;
 
        for (; ; ) {
            nowX = dirX[direction] + nowX;
            nowY = dirY[direction] + nowY;
 
            // 범위를 벗어나면 벽에 부딪혔기 때문에 방향을 반대로 전환
            if (!rangeCheck(nowX, nowY)) {
                direction = backDirection(direction);
                // 방향만 바꿔주고 다음턴에서 다시 움직임
                hitCount++;
 
            } else {
                if (map[nowX][nowY] == 0 && nowX == startX && nowY == startY) {
                    result = Math.max(result, hitCount);
                    return;
                } else if (map[nowX][nowY] == 1) {
                    if (direction == 0) {
                        // 상 -> 하
                        direction = backDirection(direction);
                    } else if (direction == 1) {
                        // 하 -> 우
                        direction = 3;
                    } else if (direction == 2) {
                        // 좌 -> 상
                        direction = 0;
                    } else {
                        // 우 -> 좌
                        direction = backDirection(direction);
                    }
 
                    hitCount++;
                } else if (map[nowX][nowY] == 2) {
                    if (direction == 0) {
                        // 상 -> 우
                        direction = 3;
                    } else if (direction == 1) {
                        // 하 -> 상
                        direction = backDirection(direction);
                    } else if (direction == 2) {
                        // 좌 -> 하
                        direction = 1;
                    } else {
                        // 우 -> 좌
                        direction = backDirection(direction);
                    }
 
                    hitCount++;
                } else if (map[nowX][nowY] == 3) {
                    if (direction == 0) {
                        // 상 -> 좌
                        direction = 2;
                    } else if (direction == 1) {
                        // 하 -> 상
                        direction = backDirection(direction);
                    } else if (direction == 2) {
                        // 좌 -> 우
                        direction = backDirection(direction);
                    } else {
                        // 우 -> 하
                        direction = 1;
                    }
 
                    hitCount++;
                } else if (map[nowX][nowY] == 4) {
                    if (direction == 0) {
                        // 상 -> 하
                        direction = backDirection(direction);
                    } else if (direction == 1) {
                        // 하 -> 좌
                        direction = 2;
                    } else if (direction == 2) {
                        // 좌 -> 우
                        direction = backDirection(direction);
                    } else {
                        // 우 -> 상
                        direction = 0;
                    }
 
                    hitCount++;
                } else if (map[nowX][nowY] == 5) {
                    direction = backDirection(direction);
                    hitCount++;
                } else if (map[nowX][nowY] == -1) {
                    result = Math.max(result, hitCount);
                    return;
                } else if (map[nowX][nowY] >= 6 && map[nowX][nowY] <= 10) {
                    // System.out.println(map[nowX][nowY]);
                    Coordinates wormCoor = findWormhole(map[nowX][nowY], nowX, nowY);
                    nowX = wormCoor.x;
                    nowY = wormCoor.y;
                }
            }
        }
         
    } // End of DFS
 
    private static int backDirection(int dir) {
        if (dir == 0) {
            return 1;
        } else if (dir == 1) {
            return 0;
        } else if (dir == 2) {
            return 3;
        } else {
            return 2;
        }
    } // End of backDirection
 
    private static Coordinates findWormhole(int holeNum, int nowX, int nowY) {
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == holeNum && (nowX != i || nowY != j)) {
                    return new Coordinates(i, j);
                }
            }
        }
 
        return null;
    } // End of findWormhole
 
    private static boolean rangeCheck(int nowX, int nowY) {
        return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N;
    } // End of rangeCheck
 
    private static void init() {
        map = new int[N][N];
        result = -1;
    } // End of init
} // End of Main class