👀 문제
https://www.acmicpc.net/problem/1987
👊 도전
1. 설계
- DFS를 이용하여 경로를 탐색하고, 중복 알파벳이 있으면 탈출한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int r,c;
static char map[][];
static boolean alpha[];
static int[] dotX= {0,1,0,-1};
static int[] dotY= {1,0,-1,0};
static int max=1;
public static void dfs(int x, int y, int cnt) {
alpha[map[x][y]-'A']=true;
for(int i=0;i<4;i++) {
int xx=x+dotX[i];
int yy=y+dotY[i];
if(0>xx||xx>=r || 0>yy||yy>=c) continue;
int next=map[xx][yy]-'A';
if(!alpha[next]) dfs(xx, yy, cnt+1);
}
max=Math.max(max, cnt);
alpha[map[x][y]-'A']=false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
r=scan.nextInt();
c=scan.nextInt();
map=new char[r][c];
alpha=new boolean[26];
for(int i=0;i<r;i++) {
String str=scan.next();
for(int j=0;j<c;j++) {
map[i][j]=str.charAt(j);
}
}
dfs(0,0,1);
System.out.println(max);
}
}
3. 결과
🤟 성공 🤟
사실 실패도 찾아본 반례 예시들이 다 돌아가서 뭐가 틀렸었던건지 아직도 잘 모르겠다. max값 갱신과 visit false처리 위치를 for문 밖으로 빼주었더니 성공하였다.
4. 설명
- DFS를 이용한다
- 상하좌우로 움직여 이동할 수 있는 최대 칸을 구해야하므로 DFS를 이용한다.
- map에 알파벳을 char형으로 저장하고, alpha를 통해 방문한 위치의 알파벳을 true로 저장하여 중복을 체크한다.
- xx, yy는 상하좌우로 움직일 수 있는 위치를 나타내며 map의 인덱스 범위를 벗어나지 않는다면 alpha를 통해 새 알파벳이라면 재귀 호출로 그곳으로 이동한다.
- for문에서 상하좌우로 더이상 움직일 수 없다면(인덱스를 벗어나거나 새로운 알파벳이 아닌 경우), for문을 탈출하여 지금까지의 cnt를 Math.max로 최댓값을 저장한다. 그리고 다음 사용을 위해 alpha[x][y]=false 한다.