Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 최소신장트리
- 객체 지향
- 생성자
- 추상 클래스
- nextInt
- enum
- 열거형
- 버퍼비우기
- this
- 캡슐화
- abstract
- Encapsulation
- 다형성
- Final
- java
- python
- Scanner
- 인터페이스
- 백준
- 프림알고리즘
- 내부 클래스
- 객체지향
- 제네릭
- 상속
- 와일드카드
- polymorphism
- 17472
- inheritance
- 추상화
Archives
- Today
- Total
쫑쫑이의 블로그
백준 1987 알파벳 Java [DFS] 본문
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
알파벳을 아스키코드로 바꿔서 65씩 빼주면 0 ~ 25 사이의 숫자로 표현 가능하다
크기가 26인 방문 배열을 만들어 알파벳 방문체크해가면서 dfs로 탐색하면 된다
import java.awt.*;
import java.io.*;
import java.util.*;
public class Main {
static int count, X, Y;
static boolean[] vtd;
static int[][] chart;
static Point[] dir = new Point[]{new Point(1, 0), new Point(-1, 0), new Point(0, -1), new Point(0, 1)};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
vtd = new boolean[26];
chart = new int[X][Y];
count = 0;
for (int x = 0; x < X; x++) {
chart[x] = br.readLine().chars().map(e -> e-65).toArray();
}
vtd[chart[0][0]] = true;
dfs(0, 0, 1);
System.out.println(count);
}
static void dfs(int x, int y, int cnt) {
if (cnt > count) count = cnt;
for (Point p : dir) {
int nx = p.x + x, ny = p.y + y;
if (isRange(nx, ny) && !vtd[chart[nx][ny]]) {
vtd[chart[nx][ny]] = true;
dfs(nx, ny, cnt + 1);
vtd[chart[nx][ny]] = false;
}
}
}
static boolean isRange(int x, int y) {
return (x >= 0 && y >= 0 && x < X && y < Y) ? true : false;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 2252 줄 세우기 Java [위상정렬] (0) | 2022.11.14 |
---|---|
백준 2239 스도쿠 Java [백트래킹, DFS] (0) | 2022.11.13 |
백준 2568 전깃줄 - 2 Java [LIS] (0) | 2022.11.11 |
백준 4386 별자리 만들기 Java [최소스패닝트리, 프림] (0) | 2022.11.10 |
백준 1766 문제집 Java [위상정렬, 우선순위 큐] (0) | 2022.11.08 |