[자바] 백준 1987번: 알파벳

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

1987번: 알파벳

첫 시도 메모리 초과로 실패

아마 StringBuffer를 너무 많이 사용해서 그런 듯 하다.

-실패한 코드

 

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

public class P1987 {
	static char[][] board;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int r, c, result;

	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());
		board = new char[r][c];

		for (int i = 0; i < r; i++) {
			String str = br.readLine();
			for (int j = 0; j < c; j++) {
				board[i][j] = str.charAt(j);

			}

		}

		bfs();

		System.out.println(result);

	}

	static void bfs() {

		Queue<Integer> q_x = new LinkedList<>();
		Queue<Integer> q_y = new LinkedList<>();
		Queue<StringBuffer> q_alphabets = new LinkedList<>();

		q_x.add(0);
		q_y.add(0);
		q_alphabets.add((new StringBuffer()).append(board[0][0]));
		while (!q_x.isEmpty()) {
			int now_x = q_x.poll();
			int now_y = q_y.poll();
			StringBuffer now_alphabets = q_alphabets.poll();

			for (int i = 0; i < 4; i++) {
				int next_x = now_x + dx[i];
				int next_y = now_y + dy[i];

				if (next_x < 0 || next_x > c - 1 || next_y < 0 || next_y > r - 1)
					continue;

				if (now_alphabets.toString().indexOf(board[next_y][next_x]) == -1) {

					if (now_alphabets.length() + 1 > result)
						result = now_alphabets.length() + 1;

					StringBuffer next_alphabets = new StringBuffer(now_alphabets);
					next_alphabets.append(board[next_y][next_x]);
					q_x.add(next_x);
					q_y.add(next_y);
					q_alphabets.add(next_alphabets);
				}
			}

		}
	}

}

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

public class P1987 {
	static char[][] board;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static boolean[] alpha = new boolean[26];
	static int r, c, result;

	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());
		board = new char[r][c];

		for (int i = 0; i < r; i++) {
			String str = br.readLine();
			for (int j = 0; j < c; j++) {
				board[i][j] = str.charAt(j);

			}

		}

		backtracking(0, 0, 1);
		System.out.println(result);

	}

	static void backtracking(int x, int y, int len) {
		alpha[board[y][x] - 'A'] = true;
		result = Math.max(result, len);
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx > c - 1 || ny > r - 1 || nx < 0 || ny < 0)
				continue;
			if (alpha[board[ny][nx] - 'A'] == false) {
				backtracking(nx, ny, len + 1);
				alpha[board[ny][nx] - 'A'] = false;
			}

		}
	}

}

 

저번에 사용했던 순열 알고리즘처럼

모든 경우의 수를 확인하기 위해 백트래킹을 사용.