[백준] 1987번 알파벳 자바

문제 (골드4)

 

1987번: 알파벳

 

 

문제 풀이

 

문제보고 바로 DFS문제라고 생각했고, visted배열을 받아 방문 여부를 표시하며 알파벳 방문 최대값을 구하면 될 것이라고 생각하고 풀었다. 그리고 방문 알파벳은 ArrayList<Character>에 담아서 contains()함수 사용해서 구별하려고 했는데, DFS실행 시, 방문했다가 나온 알파벳을 다시 지우기가 힘들었다. remove함수에서 계속 오류가 발생했다. (왜그런지 아직도 모르겠음ㅠ)

 

구글링해보니까 알파벳 개수만큼 boolean배열을 받아 여기에 방문 표시를 하는 걸 알고 바로 수정하고 풀었다.

char형 알파벳에서 아스키코드표를 보고 'A' 나 65를 빼서 숫자로 만들어 그 숫자에 해당하는 배열에 방문표시를 했다.

 

 

소스 코드

 

import java.util.Scanner;

public class Main {
	
	static char[][] board;
	static int[] dx = {-1, 1, 0, 0};			// 상하우좌
	static int[] dy = {0, 0, 1, -1};
	static int R, C;
	static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		board = new char[R][C];
		boolean[] visited = new boolean[26]; // 알파벳 개수
		
		for(int i = 0; i < R; i++) {
			String str = sc.next();
			for(int j = 0; j < str.length(); j++)
				board[i][j] = str.charAt(j);
		}
		
		dfs(0, 0, visited, 0);
		System.out.println(answer);
		sc.close();
	}
	
	public static void dfs(int r, int c, boolean[] visited, int count) {
		//System.out.println(count);
		if(answer < count)		// 최대 알파벳 방문개수 구하기 위해
			answer = count;
		
		if(visited[board[r][c]-65] == true)	// 알파벳 이미 방문한 경우 리턴
			return;	
		
		visited[board[r][c]-65] = true;		// 방문 표시
		//path.add(board[r][c]);
		
		for(int i = 0; i < 4; i++) {			
			int x = r + dx[i];
			int y = c + dy[i];
			
			if(x >= 0 && x < R && y < C && y >= 0) {
				dfs(x, y, visited, count+1);
			}
		}
		visited[board[r][c]-65] = false;
		
	}

}

 

 

 

 2022/01/24 재풀이 코드 : 혼자서 구현 완료✨

 - 위 코드와 다른 점은 방문 여부 먼저 확인한 후 재귀호출, 그리고 어차피 알파벳에 따라 방문여부가 결정 되므로 visited배열 하나만 있으면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class b_1987 {

	static int R, C;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] board;
	static boolean[][] visited;
	static boolean[] alphabet;
	static int answer = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] temp = br.readLine().split(" ");
		
		R = Integer.parseInt(temp[0]);
		C = Integer.parseInt(temp[1]);
		board = new char[R][C];
		visited = new boolean[R][C];
		alphabet = new boolean[26];
		
		for(int i = 0; i < R; i++) {
			String temp2 = br.readLine();
			for(int j = 0; j < C; j++)
				board[i][j] = temp2.charAt(j);
		}
		
		dfs(0, 0, 0);
		System.out.println(answer+1);
	}
	
	public static void dfs(int x, int y, int total) {
		visited[x][y] = true; 			//방문 표시
		alphabet[board[x][y] - 65] = true;	//알파벳 사용표시
		
		if(answer < total)
			answer = total;			//누적한 total값으로 갱신
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && nx < R && ny >= 0 && ny < C) {
            		// 알파벳 사용 안함 && 방문 안했던 곳
				if(alphabet[board[nx][ny] - 65] == false && visited[nx][ny] == false) {
					dfs(nx, ny, total+1);		//다음 보드좌표로 이동
                    
                    //갈 수 있는 곳까지 탐색한 후 빠져나올 때 다시 방문표시 없애기
                    alphabet[board[nx][ny] - 65] = false;
                    visited[nx][ny] = false;
				}
			}
		}
	}

}