[SWEA/Java] 7699. 수지의 수지 맞는 여행

[SWEA/Java] 7699. 수지의 수지 맞는 여행

SW Expert Academy

---

문제 해석

이 문제는 R x C 크기의 격자에서 알파벳을 수집하는 최적의 경로를 찾는 것이 목표이다. 각 격자 칸에는 알파벳이 적혀 있으며, 수지는 한 번 방문한 알파벳을 다시 방문할 수 없다.

풀이 과정

이 문제는 백트래킹과 비트마스킹을 활용하여 해결된다. 알파벳의 방문 여부를 비트로 표현하면서 각 위치에서 가능한 모든 방향으로의 이동을 시도하여, 방문할 수 있는 알파벳의 최대 수를 찾는다.

• sol 함수는 현재 위치에서 상하좌우로 이동 가능한 옵션을 탐색하고, 아직 방문하지 않은 알파벳으로 이동이 가능할 경우 해당 위치로 이동하여 재귀적으로 탐색을 계속한다.
• checkKey 함수는 현재 위치의 알파벳이 이미 방문한 알파벳인지를 판단하여 이동 가능 여부를 반환한다.
• key 변수는 방문한 알파벳을 비트로 저장하여 효율적인 방문 관리를 가능하게 한다.

코드

package edu.ssafy.im.SWEA.D4.No7699;

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

public class Solution {
    private char[][] graph; // 섬의 지도를 나타내는 2차원 배열
    private int key; // 방문한 알파벳을 비트로 표현하는 변수
    private int ans; // 방문할 수 있는 알파벳의 최대 수
    private int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 이동할 수 있는 네 방향을 나타내는 배열

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력

        for (int t = 1; t <= testCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()); // 행의 수
            int c = Integer.parseInt(st.nextToken()); // 열의 수

            graph = new char[r][c]; // 지도 초기화
            for (int x = 0; x < r; x++) {
                String string = br.readLine();
                for (int y = 0; y < c; y++) {
                    graph[x][y] = string.charAt(y); // 알파벳 입력
                }
            }
            key = 1 << graph[0][0] - 'A'; // 시작 지점의 알파벳 방문 처리
            ans = 0;

            sol(0, 0, 1); // 최대 방문 알파벳 수 계산 시작

            sb.append("#").append(t).append(" ").append(ans).append("\n"); // 결과 문자열 추가
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol(int x, int y, int depth) {
        ans = Math.max(ans, depth); // 최대 방문 알파벳 수 갱신

        for (int d = 0; d < direction.length; d++) {
            int nx = x + direction[d][0];
            int ny = y + direction[d][1];

            if(checkStatus(nx, ny)) { // 이동 가능한 위치인지 확인
                if(checkKey(nx, ny)) { // 방문하지 않은 알파벳인지 확인
                    key |= 1 << graph[nx][ny] - 'A'; // 알파벳 방문 처리
                    sol(nx, ny, depth + 1); // 재귀적으로 탐색 계속
                    key -= 1 << graph[nx][ny] - 'A'; // 방문 처리 해제
                }
            }
        }
    }

    private boolean checkStatus(int x, int y) {
        return 0 <= x && x < graph.length && 0 <= y && y < graph[0].length; // 격자 범위 내인지 확인
    }

    private boolean checkKey(int x, int y) {
        return (key & (1 << graph[x][y] - 'A')) == 0; // 해당 알파벳이 방문되지 않았는지 확인
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 최악의 경우 O(4^(R×C))이 될 수 있다. 각 지점에서 네 방향으로의 이동을 모두 고려해야 하기 때문에 계산량이 많아질 수 있다.

느낀점

비트마스킹과 백트래킹을 활용하여 복잡한 탐색 문제를 효율적으로 해결할 수 있는 방법을 학습하였다. 이러한 기법은 다양한 최적화 문제에 활용될 수 있으며, 효율적인 문제 해결을 위한 중요한 도구임을 이해하였다.