백준 1987번 - 알파벳

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

1987번: 알파벳

 

 

 

 

 

1년 전에 풀었으나 모든 테스트 케이스를 통과하지 못하여 실패로 남아있던 문제이다. 다시 풀었는데도 같은 로직으로 이해하고 풀게 된다. 분명 맞는 것 같은데 안되니까 답답해서 결국 정답 코드와 계속 비교한 끝에 정답을 도출해낼 수 있었다.

 

 

 

 

코드 - 실패

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

public class Main {
	static int R, C;
	static char[][] graph;
	static boolean[][] visited;
	static ArrayList<Character> letters;
	static int count;
	static int max= 0;
	
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().split(" ");
		
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		
		graph = new char[R + 1][C + 1];
		visited = new boolean[R + 1][C + 1];
		
		for(int i = 1; i <= R; i++) {
			String row = br.readLine();
			
			for(int j = 0; j < C; j++) {
				graph[i][j + 1] = row.charAt(j);
			}
		}
		
		letters = new ArrayList<Character>();
		count = 1;
		dfs(1, 1);
		
		System.out.println(max);
	}

	private static void dfs(int v1, int v2) {
		visited[v1][v2] = true; //정점 방문
		letters.add(graph[v1][v2]);
		
		for(int i = 0; i < 4; i++) { //상하좌우 탐색
			int nx = v1 + dx[i];
			int ny = v2 + dy[i];
			
			if(1 <= nx && nx <= R && 1 <= ny && ny <= C) { //좌표 범위 안에 있고
				if(!letters.contains(graph[nx][ny]) && !visited[nx][ny]) { //지금까지 지나온 알파벳과 다르고, 방문x라면
					dfs(nx, ny); //탐색
					count++;
				}
			}
		}
		visited[v1][v2] = false; //정점 방문 초기화!!
		max = Math.max(max, count);
	}

}

 

 

예제 입력 3번이 안된다.

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

 

 

 

 

 

나는 visited[x][y] 배열을 사용하여 좌표의 방문 중복을 막도록 했었다. 하지만 이 문제에서는 좌표의 방문 중복을 막는 것이 아니라, 문자의 중복을 막아야 한다. 즉, 알파벳만 다르다면 이전에 방문했던 좌표를 후에 방문해도 된다.

 

따라서 문자의 방문 여부를 체크할 26칸 짜리 배열을 만들어야 한다. 아스키 코드를 참고하여 인덱스는 문자 - 'A'로 해줘야 0번부터 들어가게 된다.

 

그리고 더 이상 탐색하지 못하면, 함수를 끝내기 전에 문자의 방문 여부를 false 처리해줘야 한다. 그리고 max 값도 갱신해준다. (근데 이 부분이 계속 재귀가 종료될 때마다 호출된다.. 어떻게 개선할 수 없나..?) 

 

 

 

 

 

코드 - 성공

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

public class b1987 {
	static int R, C;
	static char[][] graph;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static boolean[] alphabet;
	static int count;
	static int max;

	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 char[R + 1][C + 1];
		
		for(int i = 1; i <= R; i++) {
			String row = br.readLine();
			
			for(int j = 1; j <= C; j++) {
				graph[i][j] = row.charAt(j - 1);
			}
		}
		
		alphabet = new boolean[26];
		count = 1;
		max = 0;
		
		dfs(1, 1, 1);
		
		System.out.println(max);
	}

	public static void dfs(int x, int y, int count) {	
		alphabet[graph[x][y] - 'A'] = true; //알파벳 중복 안되게 처리
		
		for(int i = 0; i < 4; i++) { //상하좌우 탐색
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(1 <= nx && nx <= R && 1 <= ny && ny <= C) { //좌표 범위 안에 있고
				if(!alphabet[graph[nx][ny] - 'A']) { //지금까지 지나온 알파벳과 다르면
					dfs(nx, ny, count + 1); //탐색
				}
			}
		}
		
		//탐색 끝남
		alphabet[graph[x][y] - 'A'] = false;
		max = Math.max(max, count);
	}

}

 

 

 

 

 

결과