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

문제

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

1987번: 알파벳

설명

DFS, 백트래킹을 이용해 구현

(0, 0)부터 시작해서 상하좌우 이차원 배열 범위를 넘지 않고, 방문하지 않았던 곳으로 이동

이동할 곳에 있는 알파벳이 지금까지 DFS를 돌며 만들어진 문자열 str에 포함되지 않는 문자라면 str에 추가하고 길이도 +1

가장 최장 길이를 구해야 하기 때문에 매 DFS마다 길이 length와 최장 길이를 저장할 ans의 값을 비교해 업데이트 해주면 됨

전체 코드

import java.util.Scanner;

public class Main {
	static String[][] map;
	static boolean[][] visited;
	static int R, C;
	static int ans = 0;
	
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		
		map = new String[R][C];
		visited = new boolean[R][C];
		
		sc.nextLine();
		
		for(int i = 0; i < R; i++) {
			String temp = sc.nextLine();
			
			for(int j = 0; j < C; j++) {
				map[i][j] = temp.charAt(j) + "";
			}
		}
		visited[0][0] = true;
		dfs(0, 0, map[0][0], 1);
		
		System.out.println(ans);
	}
	
	public static void dfs(int x, int y, String str, int length) {
		if(ans < length) {
			ans = length;
		}
		
		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 || visited[nx][ny])
				continue;
			
			if(!str.contains(String.valueOf(map[nx][ny]))) {
				visited[nx][ny] = true;
				dfs(nx, ny, str+map[nx][ny], length+1);
				visited[nx][ny] = false;
			}
		}
	}

}

GITHUB

https://github.com/KwonMinha/BOJ/blob/master/BOJ%231987/src/Main.java

KwonMinha/BOJ