[삼성 SW Expert Academy] 7699. 수지의 수지맞는 여행 (JAVA)

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG

SW Expert Academy

 

풀이 아이디어 :

 - bfs 로 접근해서 풀려고 했으나, 가장 깊이 탐색 하는 경우의 수를 구하는 것이므로 dfs가 유리하다.

 - 가장 큰 값을 찾는 경우에는 모든 경우의 수를 탐색 해야하기 때문에 완전탐색의 문제라고 해석했다.

 

어려웠던 점 : 

 - (0,0) 에서 출발해 0,1 0,2 모두 출발지점으로 삼아서 가장 많은 횟수를 탐색하는 문제로 착각해 오래 걸렸다.

 -> 문제를 잘 읽자.

 

코드 :

import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static boolean[] visit = new boolean[26]; // 대문자 A ; 65 --> 0 으로 Z : 90 --> 25
	static int T; // tc
	static int R, C;

	static int[][] map;
	static int cnt;
	static int max_sub = Integer.MIN_VALUE;

	static void dfs(int r, int c, int cnt) {

		// 더이상 갈데 없으면 cnt 값 리턴

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];

			if (nr < 0 || nc < 0 || nr >= R || nc >= C)
				continue; // boundary check

			// 만약 방문한적 없는 곳이라면
			if (!visit[map[nr][nc] - 65]) {
				// 방문처리 해주고
				visit[map[nr][nc] - 65] = true;

				dfs(nr, nc, cnt + 1); // 한 칸 이동
				visit[map[nr][nc] - 65] = false; // 다시 되돌리기

			}
		}
		max_sub = Math.max(cnt, max_sub);
		
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		Queue<Point> queue = new LinkedList<>();

		T = sc.nextInt(); // testcase
		for (int tc = 1; tc <= T; tc++) {

			R = sc.nextInt();
			C = sc.nextInt();

			map = new int[R][C];
			max_sub = Integer.MIN_VALUE;
			visit = new boolean[26];
			// store
			for (int r = 0; r < R; r++) {
				String str = sc.next();
				for (int c = 0; c < C; c++) {
					map[r][c] = str.charAt(c);
				}
			}

			visit[map[0][0] - 65] = true; // 들어오자마자 방문체
			dfs(0, 0, 1);

			System.out.println("#" + tc + " " + max_sub);
		}

	}

}