[Java/백준/백트레킹] 1987번: 알파벳

 

문제

www.acmicpc.net/problem/1987

1987번: 알파벳

 

백트래킹 너무 어렵다ㅠㅠ.... 일단 백트래킹이란 걸 처음에 알아보는 것부터 아직 어설프다...

앞으로 DFS를 사용해야 할 것 같다, 가지치기 할 수 있을 것 같다 하면 걍 백트래킹으로 해야지..

 

시행착오가 좀 있었다.

처음엔 alphabet을 사용했는지 여부만 알아보는 코드이다. 

기저조건은 그냥 썼던 알파벳일때 return

max는 다 dfs를 돌고 나왔다 싶을 해줬다. 근데 이러면 안될 것 같음..ㅎㅎ 

 

package com.ssafy.hw12;

import java.io.*;
import java.util.StringTokenizer;

/* 알파벳 사용 여부만 사용 */
public class BOJ1987_2 {

	static int r;
	static int c;
	static char[][] map;
	static boolean[] alphabet = new boolean[26];
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int max = Integer.MIN_VALUE;

	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++) {
			map[i] = br.readLine().toCharArray();
		}

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

	private static void dfs(int y, int x, int cnt) {
		if (alphabet[map[y][x] - 'A'])
			return;

		alphabet[map[y][x] - 'A'] = true;

		boolean flag = false;

		for (int i = 0; i < 4; i++) {
			int tmpy = y + dy[i];
			int tmpx = x + dx[i];

			if (tmpy < 0 || tmpy >= r || tmpx < 0 || tmpx >= c || alphabet[map[tmpy][tmpx] - 'A'])
				continue;

			flag = true;
			dfs(tmpy, tmpx, cnt + 1);
			alphabet[map[tmpy][tmpx] - 'A'] = false;
		}

		if (!flag) {
			max = Math.max(max, cnt);
		}

	}

}

 

 

아니나 다를까 엄청난 실행시간이다ㅠ

 

 

 

그 다음으로는 비트연산을 사용했다!

이 방법을 사용하면 해당 노드에 방문했는지도 알 수 있고, 어떤 알파벳을 거쳤는지도 알 수 있다.

map과 같은 크기의 alphabet 배열을 만들어서 여기에 위 내용을 저장한다.

 

& : 해당 알파벳이 사용되는지 여부

| : 해당 알파벳 사용한다고 표시

 

기저조건은 해당 노드를 방문했을 때 방문했고, 방문한 알파벳이 같을 때 → 같은 경로라고 인식! return한다.

 

2 4

CAAB

ADCB

 

map[0][0] = 'C' 라면 

1 << 2 이므로 4=100 이 visited로 대입된다.

 

dfs 함수의 for문 내 if문에서

(visited & 1<< [tmpy][tmpx] - 'A') 이라고 하자.

visited가 예를 들어 7 = 111(A, B, C) 일 때, visited = 8이라면

이 결과는 100 & 111 이므로 100이다.

0이 아니면 방문했다는 뜻이다.

 

dfs를 재귀호출하는 부분에서

visited | 1 << (map[tmpy][tmpx] - 'A')

은 현재 방문 알파벳을 나타내는 visited에 방문할 위치의 알파벳을 또 표시해주는 것이라고 보면 된다.

 

휴 어려웠다...

 

package com.ssafy.hw12;

import java.io.*;
import java.util.StringTokenizer;

/* 비트 연산 사용 */
public class BOJ1987 {

	static int r;
	static int c;
	static char[][] map;
	static int[][] alphabet;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int max = Integer.MIN_VALUE;

	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];
		alphabet = new int[r][c];

		for (int i = 0; i < r; i++) {
			map[i] = br.readLine().toCharArray();
		}

		dfs(0, 0, 1, 1 << (map[0][0] - 'A'));
		System.out.println(max);
		br.close();
	}

	private static void dfs(int y, int x, int cnt, int visited) {
		if (alphabet[y][x] == visited)
			return;

		alphabet[y][x] = visited;
		max = Math.max(max, cnt);

		for (int i = 0; i < 4; i++) {
			int tmpy = y + dy[i];
			int tmpx = x + dx[i];

			if (tmpy < 0 || tmpy >= r || tmpx < 0 || tmpx >= c || (visited & 1 << (map[tmpy][tmpx] - 'A')) != 0)
				continue;

			dfs(tmpy, tmpx, cnt + 1, visited | 1 << (map[tmpy][tmpx] - 'A'));
		}
	}

}