백준 1107 게임(Gold 2, Python, Java)
DFS + DP 문제를 풀어봅시다!
문제
형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.
일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.
- 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
- 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
- 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.
만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.
보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.
입력
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.
정답
Python
import sys
sys.setrecursionlimit(10 ** 5)
dxs, dys = (1, -1, 0, 0), (0, 0, 1, -1)
n, m = map(int, sys.stdin.readline().rstrip().split())
g = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[False for _ in range(m)] for __ in range(n)]
dp = [[0 for _ in range(m)] for __ in range(n)]
ans = 0
def in_range(a, b):
return 0 <= a < m and 0 <= b < n
def dfs(a, b, depth):
global ans
ans = max(ans, depth)
step = int(g[b][a])
for dx, dy in zip(dxs, dys):
nx, ny = a + dx * step, b + dy * step
if in_range(nx, ny) and g[ny][nx] != 'H' and depth + 1 > dp[ny][nx]:
if visited[ny][nx]:
print(-1)
exit()
else:
dp[ny][nx] = depth + 1
visited[ny][nx] = True
dfs(nx, ny, depth + 1)
visited[ny][nx] = False
visited[0][0] = True
dfs(0, 0, 1)
print(ans)
Java
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static StringBuilder sb = new StringBuilder();
private static StringTokenizer st;
private static int[] dxs = {1, -1, 0, 0}, dys = {0, 0, -1, 1};
private static int n, m;
private static char[][] g;
private static int[][] dp;
private static boolean[][] visited;
private static int ans = 0;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
g = new char[n][m];
dp = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String cur = st.nextToken();
for (int j = 0; j < m; j++) {
g[i][j] = cur.charAt(j);
dp[i][j] = 0;
visited[i][j] = false;
}
}
visited[0][0] = true;
dfs(0, 0, 1);
sb.append(ans);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static boolean inRange(int x, int y) {
return 0 <= x && x < m && 0 <= y && y < n;
}
static void dfs(int x, int y, int depth) {
if (ans == -1) return;
ans = Math.max(ans, depth);
int step = g[y][x] - '0';
for (int i = 0; i < 4; i++) {
int nx = x + dxs[i] * step, ny = y + dys[i] * step;
if (inRange(nx, ny) && g[ny][nx] != 'H' && depth + 1 > dp[ny][nx]) {
if (visited[ny][nx]){
ans = -1;
return;
} else {
dp[ny][nx] = depth + 1;
visited[ny][nx] = true;
dfs(nx, ny, depth + 1);
visited[ny][nx] = false;
}
}
}
}
}
풀이
DFS를 이용해서 푸는 문제입니다!! 그런데 DP가 추가된… 처음에는 DP 를 사용하지 않고 풀었는데… 6%에서 가차없이 시간초과가 나더라고요
그래서 시간복잡도를 최대한 줄이기 위해서 어떻게 해야 하나 궁금했는데, 해당 문제의 게시판에서는 다들 DP를 이용해서 풀었다길래 DP 배열을 이용해서 풀려고 시도했습니다.
바로 DFS를 전진(?) 시키는 부분에서 사용했습니다. 동서남북 방향으로 진행하려고 하는데, 내가 진행했을 때에 더 오래 살아 남았다면 (depth + 1 > dp[ny][nx]) 전진시킵니다.
그리고 전진했는데 만약에 이전에 방문을 했던 위치이다??(visited[ny][nx] == true (or True)) 그러면 사이클 내부에 진입을 한 것이므로 무조건 무한히 돌 수 있으므로 -1을 출력합니다.
처음 방문하는 위치라면, 내가 더 오래 살아남았으므로 dp 배열을 갱신해주고 방문 여부를 해당 노드를 방문해 줍니다.
