[백준/1987] 알파벳 - Java 자바

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

 

개념: dfs, 백트래킹

 

 

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행, 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

 

---

 

 

풀이

처음에는 그래프를 String으로 입력 받아서 푸느라 Set을 사용했다. 통과는 하지만 효율성이 썩 좋지 못하다.. dfs나 백트래킹에 맞는 풀이도 아닌거 같고?

그래프를 int로 입력 받았더니 효율성이 개선됐다. `graph[i][j] = str.charAt(j)-'A';`

 

전체코드

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

public class Main {
	static int R,C;
	static int[][] graph;
	static boolean[] checked;
	static int answer;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		graph = new int[R][C];
		checked = new boolean[26];

		for(int i = 0; i < R; i++) {
			String str = br.readLine();
			for(int j = 0; j < C; j++) {
				graph[i][j] = str.charAt(j)-'A';
			}
		}

		dfs(0,0,0);
		System.out.println(answer);
	}
	
	static void dfs(int x, int y, int cnt) {
        checked[graph[x][y]] = true;
        answer = Math.max(answer, cnt + 1);  // 현재 위치도 포함해서 카운트
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

            if(!checked[graph[nx][ny]]) {  // 방문하지 않은 알파벳인 경우에만 진행
                dfs(nx, ny, cnt + 1);
            }
        }
        
        checked[graph[x][y]] = false;
    }
}

 

 

이전코드

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

public class Main {
    static int R, C, answer;
    static String[][] graph;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static HashSet<String> set = new HashSet<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new String[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = String.valueOf(str.charAt(j));
            }
        }

        set.add(graph[0][0]);
        dfs(0, 0, 1);
        System.out.println(answer);
    }

    public static void dfs(int x, int y, int count) {
        answer = Math.max(count, answer);

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < R && 0 <= ny && ny < C && !visited[nx][ny]) {
                if (!set.contains(graph[nx][ny])) {
                    visited[nx][ny] = true;
                    set.add(graph[nx][ny]);
                    dfs(nx, ny, count + 1);
                    visited[nx][ny] = false;
                    set.remove(graph[nx][ny]);
                }
            }
        }
    }
}