[백준/java] 1987번 : 알파벳 - DFS

1987번 : 알파벳

 

728x90

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

1987번: 알파벳

 

문제풀이 처음으로 DFS를 사용해서 풀어봤다.

 

반응형

 

골드 4 난이도 치고는 문제 자체는 어렵지 않다

 

나왔던 알파벳이 또 나오면 더 이상 진행하지만 않으면 되는데,

 

나는 HashSet을 이용하여 중복으로 나온건지 체크하였다.

 

package dfs;

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

public class Alphabet {
	static char[][] map;
	static Set<Character> set = new HashSet<Character>();
	static int R, C, max;
	static int[] dy = { 1, 0, -1, 0 };
	static int[] dx = { 0, 1, 0, -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());

		map = new char[R][C];

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

		dfs(0, 0);
		System.out.println(max);
	}

	public static void dfs(int y, int x) {
		if (set.contains(map[y][x]))
			return;
		set.add(map[y][x]);
		max = Math.max(max, set.size());

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

			if (ny < 0 || ny >= R || nx < 0 || nx >= C)
				continue;
			if (set.contains(map[ny][nx]))
				continue;

			dfs(ny, nx);
			set.remove(map[ny][nx]);
		}
	}
}