문제
https://www.acmicpc.net/problem/17090
풀이
dfs + dp로 풀이했다. delta 배열의 인덱스에 맞춰 map 배열을 초기화한다. 배열을 돌면서 아직 방문하지 않은 곳이면 칸에 적힌대로 이동하고, 탈출할 수 있으면 지나온 경로를 모두 true로, 탈출할 수 없으면 지나온 경로를 모두 false로 나타내면서 탈출 가능한 칸의 수를 카운팅한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N, M, answer;
static int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int[][] map;
static boolean[][] dp, visited;
public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
dp = new boolean[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String str = in.readLine();
for (int j = 0; j < M; j++)
map[i][j] = str.charAt(j) == 'U' ? 0 : str.charAt(j) == 'D' ? 1 : str.charAt(j) == 'L' ? 2 : 3;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!visited[i][j]) {
visited[i][j] = true;
dfs(i, j);
}
}
}
System.out.println(answer);
}
static void dfs(int r, int c) {
int dr = r + delta[map[r][c]][0];
int dc = c + delta[map[r][c]][1];
if (dr < 0 || dc < 0 || dr >= N || dc >= M || (visited[dr][dc] && dp[dr][dc])) {
dp[r][c] = true;
answer++;
return;
}
if (visited[dr][dc]) {
dp[r][c] = false;
return;
}
visited[dr][dc] = true;
dfs(dr, dc);
dp[r][c] = dp[dr][dc];
if (dp[r][c])
answer++;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ 백준] 12764 - 싸지방에 간 준하, Java(자바) (0) | 2023.03.07 |
---|---|
[BOJ - 백준] 14923 - 미로탈출, Java(자바) (0) | 2023.03.07 |
[BOJ 백준] 1991 - 트리 순회, Java(자바) (0) | 2023.03.04 |
[BOJ 백준] 6068 - 시간 관리하기, Java(자바) (0) | 2023.03.03 |
[BOJ 백준] 7576 - 토마토, Java(자바) (0) | 2023.03.02 |