접근 방법

  • dfs로 접근해야 하는 문제이다.
  • 주어진 2차원 배열의 모든 정점에 대하여 탐색을 진행해야 한다. 이를 위해 상하좌우를 비교할 때 많이 사용되는 형식인 다음 두 배열을 전역으로 선언하여 사용한다.

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

  • 또한 BufferedReader를 이용하여 입출력의 효율을 개선시켰다.
  • 가능한 모든 요소들의 중복을 제거하기 위해서 HashSet을 사용하려다가 ArrayList의 isContain을 사용하여 해결했다.

dfs()

  • 역시 자주 쓰던 그 dfs다. 중복 없는 결과를 가져오기 위해서 처음에 백트래킹을 적용 시켰다가 삽질했다. 그러다 방문했던 정점을 다시 방문할 수 있다는 조건을 뒤늦게 다시 알아차렸고 접근 방법에서 말했던 것 처럼 dfs의 기저 조건을 판별하는 부분에서 중복 제거를 수행 해 주었다.

public class BOK2210 {
   static int[] dx = {0, -1, 0, 1};
   static int[] dy = {-1, 0, 1, 0};

   public static int[][] arr = new int[5][5];
   public static List answer = new ArrayList<String>();

   public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;

       for (int i = 0; i < 5; i++) {
           // 공백 포함 읽어주기
           st = new StringTokenizer(br.readLine());
           for (int j = 0; j < 5; j++) {
               arr[i][j] = Integer.parseInt(st.nextToken());
           }
       }

       for (int i = 0; i < 5; i++) {
           for (int j = 0; j < 5; j++) {
               // 배열의 모든 요소에 대해 탐색 진행
               dfs(i, j, 0, "");
           }
       }
   }

    public static void dfs(int x, int y, int depth, String str) {

       // 6번 이동했을 때
       if (depth == 6) {
           // 중복 제거
           if (!answer.contains(str)) {
               answer.add(str);
               System.out.println(str);
           }
           return;
       }

       for (int j = 0; j < 4; j++) {
           int nowX = x + dx[j];
           int nowY = y + dy[j];
           // 주어진 형식의 범위 벗어나면 안됨
            if (0 > nowX || nowX >= 5 || 0 > nowY || nowY >= 5) {
               continue;
            }
        dfs(nowX, nowY, depth + 1, str + arr[x][y]);
       }
    }
}