[SWEA_7699 - JAVA] 수지의 수지 맞는 여행

 

 

풀이

최단 경로였다면 BFS로 풀었겠지만, 가장많이 방문한 횟수를 구해야 하느라 DFS로 구현.
map을 입력받는 즉시 숫자로 치환.
비트 마스킹을 통하여 방문여부 관리.
크게 어렵지 않았던 문제로 비트 마스킹 연습에 좋은 문제.

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int R, C, max; // 행,열
    static int[] dy = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dx = { 0, 0, -1, 1 };
    static int[][] map;
 
    public static boolean isValid(int i, int j) {
        if (i < 0 || j < 0 || i >= R || j >= C) {
            return false;
        }
        return true;
    }
 
    public static void solution(int cnt, int visited, int row, int col) {
 
        visited = visited | (1 << map[row][col]); // 방문 체크
        cnt++; // 방문한 개수
 
        max = Math.max(max, cnt);
        if (cnt == 26)
            return;
 
        int nexty, nextx;
        for (int i = 0; i < 4; i++) {
            nexty = row + dy[i];
            nextx = col + dx[i];
            if (isValid(nexty, nextx) && (visited & (1 << map[nexty][nextx])) == 0) { // 범위 검사 && 방문여부
                solution(cnt, visited, nexty, nextx);
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        String str = null;
        int tc = Integer.parseInt(br.readLine());
        for (int test = 1; test <= tc; test++) {
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken()); // 행
            C = Integer.parseInt(st.nextToken()); // 열
            map = new int[R][C];
            max = 0;
            for (int i = 0; i < R; i++) {
                str = br.readLine();
                for (int j = 0; j < C; j++) {
                    map[i][j] = str.charAt(j) - 'A';
                }
            }
 
            // ========================== 입력 ==========================
            solution(0, 0, 0, 0);
            System.out.println("#" + test + " " + max);
        }
 
    }
 
}
 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG

SW Expert Academy