[BaekJoon] 백준 1987번 _ 알파벳 for JAVA _ DFS 알고리즘

 

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

1987번: 알파벳

 

 

 

문제

 

 

 

---

 

참고 : https://settembre.tistory.com/377

 

 

  ㅡㅡㅡㅡㅡㅡㅡㅡㅡ C

ㅣ

ㅣ

ㅣ

ㅣ

ㅣ

 R

 

이런 느낌인건 탐색 써서 상하좌우 살펴봐야 한다는건 알겠는데

 

 

이 문제에서는 겹치지 않고 최대 움직일 수 있는걸 구하는 거여서 이 부분을 생각하는게 어려웠다.

 

 

 

그래서 다른분꺼 참고함

 

 

 

나는 상, 하, 우, 좌 순서로 보기 때문에

 

 

첫번째로 여기 4개를 살펴보고 더 이상 나아갈 수 없게 된다.

 

 

[0,0] -> [0,1] -> [1,1] -> [0,1] 순서로 확인하는데

 

 

내가 사용한 HashMap에 [0,1]인 F를 넣고 -> 재귀해서 [1,1]인 H를 넣고 -> 재귀해서 [0,1]인 E를 넣으니까

 

재귀가 끝나고 바로 밑 코드에 remove()로 바로 없애주면

 

 

재귀 끝

[0,1]인 E 삭제 -> [1,1]인 H 삭제 -> [0,1]인 F 삭제

 

 

가 이루어져 처음에 넣어둔 [0,0] I만 남는다.

 

그리고 다시 [0,0] 에서 '우'로 갔을 때인 [0,1]에서 나아가는 형식으로... 넣고 재귀할 때 count 더하고 바로 삭제하고...

 

 

를 반복해주면 된다.

 

 

 

코드

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


public class Baek1987 {
	public static String map[][];
	public static HashSet<String> hash = new HashSet<>();
	public static int R = 0, C = 0, answer = 0;
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -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 String[R][C];
		
		for(int i = 0; i < R; i++) { // map을 string 값으로 넣으려고 이렇게 짰는데
			String in = br.readLine();
			for(int j = 0; j < C; j++)
				map[i][j] = String.valueOf(in.charAt(j));
		}
        
//		map을 char 형식으로 만들어 편하게 배열에 넣을 수도 있다.
//		for(int i = 0; i < R; i++)
//            map[i] = br.readLine().toCharArray();
			
            
		hash.add(map[0][0]); // 먼저 넣어둠
		dfs(0,0,1);
		System.out.println(answer);

	}
	
	public static void dfs(int x, int y, int count) {

		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= -1 || nx >= R || ny <= -1 || ny >= C) continue;

			if(hash.contains(map[nx][ny])) { // 알파벳 존재하면 max 찾기
				answer = Math.max(answer, count);
			} else { // 존재 안하면
				hash.add(map[nx][ny]);
				dfs(nx, ny, count + 1);
				hash.remove(map[nx][ny]); // 다 넣고 더이상 못갈 때 hash 속 값 삭제
			}
			
		}
		
	}

}

 

 

 

참고로 HashSet 대신 ArrayList를 쓰면 시간 초과남.

 

 

검색해보니 remove할 때 시간복잡도가 O(n)이 되어서 그런 것 같다고 한다. ㅠㅠ

 

 

 

성능

 

 

 

 

HashSet 써도 성능 구려서 다른사람꺼 살펴볼거다.

 

 

 

---

 

다른 사람 코드

 

 

 

 

 

 

맞힌 사람 코드 1번에 있는 사람꺼인데 성능 내꺼랑 거의 3배 차이난다ㅎ

 

 

visit 함수 만든거 빼면 21번째 줄부터 다른데 한번 살펴보겠다.

 

 

 

비트마스크를 사용한 방법인데

 

 

우선 21번째 줄 1 << board[0][0] - 'A' 에서 -'A'를 함으로써 board[][] 값이 A이면 0 ~ Z이면 25 까지 나오게 된다.

 

긍까 board[0][0] = 'A' 이면 board[0][0] - 'A' = 0

 

board[0][0] = 'Z' 이면 board[0][0] - 'A' = 25

 

가 되는 것이다.

 

 

 

1 <<  board 어쩌구 이거는 비트 마스크를 사용한 방법으로 2진수로 표현한 1 = 00000001 이잖음

 

board[0][0] = I 라고 치면 -'A' = 8 이므로 1 << 8 = 10000000 가 됨 (2^8)

 

 

 

확인할 숫자를 n, i번째 비트 확인

n & (1 << i)가 0이라면 i번째 비트는 0, 0 초과면 i번째 비트가 1이 되는거임

 

 

그래서 (bit & (1 << board[nx][ny] - 'A')) == 0 일때만 dfs를 돌리니까 중복체크가 되는것이다.

 

 

변수 bit 비트의 다음 확인할 board[][]-'A' 번째가.. 0이려면 이전에 1이 아니었으면 됨

 

왜냐면 bit는 1을 오른쪽으로 board[][]-'A' 번 옮긴 수니까!

 

 

 

 

 

뭔말이냐면 처음에 1을 board[0][0] 만큼 옮기잖음 근데 그냥 A~Z 를 0~25 라고 치고

 

 

board[0][0] = I 이면 board[0][0]-'A' = 8 이잖아요

 

 

그래서 0000000000000000010000000 가 되는거임

 

 

board[0][0] = Z 이면 board[0][0]-'A' = 25니까

 

 

1000000000000000000000000 이 되는거임

 

 

일케 걍 배열 뭐 그런거처럼 사용하는것임

 

 

 

 

 

그리고 다음 재귀할 때의 변수 bit 값은 bit | (1 << board[nx][ny] - 'A') 이 되는데

 

 

n | (1 << i) 이면

 

i번째 비트의 값을 1로 변경하는 것이다.

 

 | 연산자의 경우, 두 비트 중 한 비트라도 1이면 1이 나오기 때문임

 

 

그래서 다음 알파벳을 0~25중 하나로 바꾼 값에 해당하는 번째의 비트를 1로 바꾸는거임

 

 

 

 

만약에 [0][0] = I 이고 그 다음 갈 값이 Z이면

 

 

0000000000000000010000000

 

 

에서 1000000000000000010000000 일케 2개가 1이 되게 해서 알파벳 들렀다고 말하는거임

 

 

 

 

 

 

이해하다가 머리 빠개질뻔했다.

 

 

https://hongjuzzang.github.io/bitmask/bit_mask/

[java] 비트 마스크

 

 

 

이 블로그가 없었다면 이해할 수 없었을것이다.. 다들 참고하세요... 비트 마스크 ㅁㅊ.....