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

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

1987번: 알파벳

풀이

말이 지날 수 있는 최대의 칸 수를 구하기 위해, DFS를 사용해서 모든 경우를 탐색해야 한다.

이 때 같은 알파벳이 적힌 칸을 두 번 지날 수 없으므로, 중복되는 알파벳이 있는지 체크하기 위해 map을 사용한다.

칸을 이동할 때마다 그 칸의 알파벳을 map의 key로 저장하고, 다음 칸으로 이동하기 전  map.containsKey() 메서드를 호출하여 다음 칸의 알파벳이 map에 있는지를 체크, 없다면 DFS를 수행한다.

map의 value는 아무거나 상관없으므로 boolean 타입을 저장한다.

주의할 점

• dfs를 시작하기 전 board[0][0]의 알파벳을 map에 추가해줘야 한다.
• DFS를 수행하고 종료되면, map에서 해당 엔트리를 삭제해줘야 한다.

로직

1. dfs를 시작하기 전 board[0][0]의 알파벳을 map에 추가한다.

2. dfs를 수행할 때마다 max 값을 업데이트한다.

3. 4개의 방향을 탐색한다.

4. 이동한 위치가 배열을 벗어나지 않고, 이동한 위치의 알파벳이 map에 없다면

• map에 해당 알파벳 추가
• dfs(nx, ny, cnt+1)
• map에서 해당 알파벳 제거

 

코드

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

public class Main {
	
	static int n, m, max = 0;
	static char[][] board;
	static HashMap<Character, Boolean> map = new HashMap<>();
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	
	public static void dfs(int x, int y, int cnt) {
		
		max = Math.max(max, cnt);
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && !map.containsKey(board[nx][ny])) {
				map.put(board[nx][ny], true);
				dfs(nx, ny, cnt+1);
				map.remove(board[nx][ny]);
			}
			
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		board = new char[n][m];
		
		for (int i = 0; i < n; i++) {
			board[i] = br.readLine().toCharArray();
		}
		
		map.put(board[0][0], true);
		dfs(0, 0, 1);
		
		System.out.println(max);
	}
	
}

 

---

다른 풀이 2

중복되는 알파벳이 있는지 체크하기 위해 map대신 boolean[] visited 배열을 사용한다. 알파벳 개수는 26개로 정해져 있기 때문에 Boolean 배열을 사용할 수 있다.

또한 dfs를 수행할 때마다 max 값을 업데이트하지 않고, 중복된 알파벳을 발견했을 때 이동거리를 갱신하고 리턴한다.

주의할 점

• visited[board[x][y] - 'A'] = true; 를 한 지점과 같은 코드 블록에서 visited[board[x][y] - 'A'] = false; 를 넣어주어야 한다.

 

나머지 로직은 같다.

 

코드

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

public class Main {
	
	static int n, m, max = 0;
	static char[][] board;
	static boolean[] visited = new boolean[26];
	
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	
	public static void dfs(int x, int y, int cnt) {
		
		if (visited[board[x][y] - 'A']) {
			max = Math.max(max, cnt);
			return;
		}
		
		visited[board[x][y] - 'A'] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				dfs(nx, ny, cnt+1);
			}
			
		}
		
		visited[board[x][y] - 'A'] = false;
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		board = new char[n][m];
		
		for (int i = 0; i < n; i++) {
			board[i] = br.readLine().toCharArray();
		}
		
		dfs(0, 0, 0);
		
		System.out.println(max);
	}
	
}

참고: https://1-7171771.tistory.com/61

 

두번째 방법이 메모리를 더 적게 쓰고 실행 시간도 작다.

중복을 체크해야 할 알파벳 등이 개수가 정해져 있다면 map을 쓰는 방법보다 boolean 배열을 사용하는 방법이 더 좋다.