[SWEA] 7699. 수지의 수지 맞는 여행

문제

평소에 여행을 즐기는 수지는 이번에 새로운 섬에 도착했다.

이 섬은 1행, 1열로 시작해서 R행, C열까지 있으며, 총 R*C 칸으로 이루어져 있다.

수지는 지금 1행 1열에 있으며 앞으로 있을 야근을 위하여 기회 있을 때 미리 여행을 떠나려고 한다.

이 섬의 각 칸에는 알파벳이 적혀있다. 이 알파벳은 섬의 명물이고, 같은 알파벳은 같은 명물이다.

이 섬에서는 명물을 볼 때마다 요금을 지급해야 하는데 각 알파벳 명물을 처음 볼 땐 무료로 볼 수 있다.

그리고, 수지는 여행을 할 때 자신이 있는 지점의 명물을 본 후 4방향(상, 하, 좌, 우) 중 한 방향으로 1칸 이동 후 다음 명물을 보는 행동을 반복한다.


올해 SGA사 1년 차인 수지는 현재 대출빚과 카드빚에 허덕이고 있다.

따라서, 명물을 최대한 많이 보되, 요금을 지급하지 않는 방법을 택해야 한다.

수지가 1행 1열에서 여행을 시작했을 때, 같은 알파벳 명물을 두 번 이상 보지 않도록 여행을 떠나는 방법 중에 볼 수 있는 명물의 최대 개수를 구하여라.

 

풀이방법

DFS(깊이 우선 탐색)알고리즘으로 해결한다.

 

한 정점을 시작으로 상, 하, 좌, 우에 인접한 노드 중 조건을 만족하는 모든 노드를 방문한다.

 

이 때의 조건은, 방문했던 노드의 알파벳과 같은 노드는 방문하지 않는다.

 

조건을 만족하는 노드를 방문해 나온 경로 중 가장 긴 경로를 출력한다.

 

소스코드

package samsung;

import java.util.*;

public class s_7699 {
	static int[][] map;
	static int n;
	static int m;
	static int[] visit;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int max;
	
	public static void dfs(int x, int y, int depth) {
		visit[map[x][y]] = 1;
		depth++;
		if(max < depth)
			max = depth;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
				if(visit[map[nx][ny]] == 0) dfs(nx, ny, depth);
			}
		}
		visit[map[x][y]] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			m = sc.nextInt();
			map = new int[n][m];
			visit = new int[100];
			max = 0;
			
			for(int i = 0; i < n; i++) {
				String s = sc.next();
				for(int j = 0; j < m; j++) {
					map[i][j] = s.charAt(j) - '0'; 
				}
			}
			
			dfs(0, 0, 0);
			
			System.out.println("#" + t + " " + max);
		}
	}
}