[알고리즘][X] 알파벳

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

1987번: 알파벳

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int count;
	static int maxCount;
	static char[][] map;
	static int R;
	static int C;
	static HashSet<Character> set;
	public static void main(String[] args) throws Exception {
		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 line = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		
		set = new HashSet<>();
		set.add(map[0][0]);
		maxCount = Integer.MIN_VALUE;
		count = 1;
		dfs(new Point(0, 0));
		System.out.println(maxCount);
	}

	private static void dfs(Point point) {
		
//		maxCount = Math.max(maxCount, count);
		int N = map.length;
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		for (int i = 0; i < 4; i++) {
			int nx = point.x + dx[i];
			int ny = point.y + dy[i];
			
			if (!(0 <= nx && nx < R && 0 <= ny && ny < C)) {
				maxCount = Math.max(maxCount, count);
				continue;
			}
			
			char alphabet = map[nx][ny];
			if (!set.add(alphabet)) {
				maxCount = Math.max(maxCount, count);
//				continue;
			} else {
				count++;
				dfs(new Point(nx, ny));
				count--;
				set.remove(alphabet);
			}
		}
		
	}
}

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int count;
	static int maxCount;
	static char[][] map;
	static boolean[][] visited;
	static int R;
	static int C;
	static HashSet<Character> set;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		visited = new boolean[R][C];
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		
		set = new HashSet<>();
		set.add(map[0][0]);
		maxCount = Integer.MIN_VALUE;
		count = 1;
		visited[0][0] = true;
		dfs(new Point(0, 0));
		System.out.println(maxCount);
	}

	private static void dfs(Point point) {
		
//		maxCount = Math.max(maxCount, count);
		int N = map.length;
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		for (int i = 0; i < 4; i++) {
			int nx = point.x + dx[i];
			int ny = point.y + dy[i];
			
			if (!(0 <= nx && nx < R && 0 <= ny && ny < C && visited[nx][ny] == false)) {
				maxCount = Math.max(maxCount, count);
				continue;
			}
			
			char alphabet = map[nx][ny];
			if (!set.add(alphabet)) {
				maxCount = Math.max(maxCount, count);
//				continue;
			} else {
				count++;
				visited[nx][ny] = true;
				dfs(new Point(nx, ny));
				visited[nx][ny] = false;
				count--;
				set.remove(alphabet);
			}
		}
		
	}
}

나의 풀이

- visited를 사용하지 않아도 된다. 왜냐하면 어차피 set.add에서 확인이 되기 때문이다. 오히려 그게 더 빠르다.

- 행과 열이 각각 R, C였는데 정방행렬이라고 생각하고 범위 체크를 할 때 둘 다 N으로 넣어 틀렸다. 조심하자!!!!