[백준-골드4]알파벳 - Java

iamjinseo·2023년 2월 26일

DFS/BFS 백준

문제풀이-Java

목록 보기

31/53

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

문제 설명

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이

R,C짜리 2차원 배열을 만들고 문자를 집어넣음. charAt으로

그리고 0,0에서 탐색을 시작하면서 현재 위치한 곳의 문자의 아스키값-65를 boolean배열에 인덱싱하여 true로 집어넣음

A를 만났을 때: 아스키코드 65이므로 A에서 65빼면 0 -> 0 인덱스 방문처리

package gold4;

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

/*
 * R,C짜리 2차원 배열을 만들고 문자를 집어넣음. charAt으로
 * 그리고 0,0에서 탐색을 시작하면서 현재 위치한 곳의 문자의 아스키값-65를 boolean배열에 인덱싱하여 true로 집어넣음
 * A를 만났을 때: 아스키코드 65이므로 A에서 65빼면 0 -> 0 인덱스 방문처리
 * */
public class B1987_알파벳 {
	static int[] di = { 0, 0, 1, -1 };
	static int[] dj = { 1, -1, 0, 0 };

	static int R, C;
	static char[][] map;
	static int res=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];
		boolean[] visit = new boolean[26]; // 알파벳을 방문했는지 나타낼것

		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		} // end input
		dfs(0,0,1, visit);
		System.out.println(res);
	}

	static void dfs(int i, int j, int depth, boolean[] visit) {
		System.out.println("============================");
		System.out.println(map[i][j]+", 아스키: "+(int)map[i][j]);
		visit[map[i][j] - 65] = true; // 현재 알파벳 방문처리
		System.out.println(map[i][j]-65+" 방문처리. visit: "+Arrays.toString(visit));
		
		for (int n = 0; n < 4; n++) {
			int ni = i + di[n];
			int nj = j + dj[n];
			System.out.println("지금 문자: "+map[i][j]);
			System.out.println("ni: "+ni+", nj:"+nj+", ");
			
			//범위검사
			if(ni<0 || ni>=R || nj<0 || nj>=C)
				continue;
			// 방문한 알파벳이면 안됨
			if(visit[map[ni][nj]-65]) { 
				System.out.println((map[ni][nj])+" 방문한 적 있음");
				continue;
			}
			
			dfs(ni, nj, depth+1, Arrays.copyOf(visit, visit.length));
		}
		res = Math.max(res, depth);
	}
}

결과

남의 코드

내 코드가 메모리도 크고 실행시간도 긴 편인데 dfs실행할 때마다 visit배열을 계속 Arrays.copyOf해서 그럴 것이다.

구글링 좀 해봤는데 겹치는 문자가 등장했을 때를 기저조건으로 놓고 res와 depth를 비교한 다음에 리턴하면 된다.

그리고 유도파트가 시작할 때에 방문처리를 하고 끝날 때 다시 미방문 처리하면 됨(대충 순열 비슷한거임)

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

public class Main {

	static int R, C;
	static int[][] map;
	static boolean[] visit = new boolean[26];
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int ans = 0;

	public static void dfs(int x, int y, int count) {
		if (visit[map[x][y]]) { // 0,0에 저장된 알파벳이 이미 한번 방문한 알파벳이라면,
			ans = Math.max(ans, count); // 정답을 갱신해준다.
			return; // 조건에 만족하므로 리턴.
		} else {
			visit[map[x][y]] = true;
			for (int i = 0; i < 4; i++) {
				int cx = x + dx[i];
				int cy = y + dy[i];

				if (cx >= 0 && cy >= 0 && cx < R && cy < C) {
					dfs(cx, cy, count + 1);
				}

			}

			visit[map[x][y]] = false;

		}
	}

	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 int[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j) - 'A';
			}
		}

		dfs(0, 0, 0);
		// (0,0)부터 시작하며, 현재 이동한 위치는 0회

		System.out.println(ans);
	}
}