백준 1103번 - 게임

문제

백준 1103번 - 게임

---

아이디어

(0, 0)부터 DFS로 최대 이동 횟수를 구하면 되는데, 특정 위치에서 최대 이동 횟수는 어차피 한번 구하면 고정된다. 따라서 재귀를 빠져나오고 다른 경로를 탐색할 때는 이전에 구한 최댓값을 활용할 수 있다.

0. 정적 변수 준비

static int n, m;
static char[][] board;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int[][] mem;
static boolean[][] visit;
static boolean flag = false;

• dx, dy는 DFS에 사용될 배열이다.
• mem 배열이 이번 아이디어의 핵심으로, mem[x][y]는 (x, y) 위치에서 가능한 최대 이동 횟수를 저장한다. 이전 분기점으로 돌아와 다른 분기점을 확인할 때 중복 탐색을 방지한다.
• flag는 무한번 움직이는 여부를 의미한다. 중간에 한번이라도 무한번 움직이는 경로가 있다면 나머지 경로는 추가로 살펴볼 필요 없다.

1. dfs 메서드

private static int dfs(int x, int y) {
    if (flag) return 0;
    
    if (mem[x][y] != -1) {
        return mem[x][y];
    }
    
    mem[x][y] = 1;
    visit[x][y] = true;
    int num = board[x][y] - '0';
    
    for (int i = 0; i < 4; i++) {
        int nx = x + (dx[i] * num);
        int ny = y + (dy[i] * num);
        
        if (nx < 0 || ny < 0 || nx >= n || ny >= m || board[nx][ny] == 'H') {
            continue;
        }
        if (visit[nx][ny]) {
            flag = true;
            return 0;
        }
        
        mem[x][y] = Math.max(mem[x][y], 1 + dfs(nx, ny));
    }
    
    visit[x][y] = false;
    return mem[x][y];
}

• 기본적으로 (x, y)위치에 도착하면 해당 위치에서 최소 한번은 움직일 수 있으므로 1로 초기화한다.
• 해당 위치에 있는 수만큼 이동하다가 사이클이 발생하면 무한번 움직이는 경우이므로 반복을 종료한다.
• 그렇지 않으면 재귀호출로 계속 타고 내려가면서 최대 이동 횟수를 갱신한다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(NM)

---

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_1103 {

    static int n, m;
    static char[][] board;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] mem;
    static boolean[][] visit;
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new char[n][m];
        mem = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
            Arrays.fill(mem[i], -1);
        }

        dfs(0, 0);

        System.out.println(flag ? -1 : mem[0][0]);
    }

    private static int dfs(int x, int y) {

        if (flag) return 0;

        if (mem[x][y] != -1) {
            return mem[x][y];
        }

        mem[x][y] = 1;
        visit[x][y] = true;
        int num = board[x][y] - '0';

        for (int i = 0; i < 4; i++) {
            int nx = x + (dx[i] * num);
            int ny = y + (dy[i] * num);

            if (nx < 0 || ny < 0 || nx >= n || ny >= m || board[nx][ny] == 'H') {
                continue;
            }
            if (visit[nx][ny]) {
                flag = true;
                return 0;
            }

            mem[x][y] = Math.max(mem[x][y], 1 + dfs(nx, ny));
        }

        visit[x][y] = false;
        return mem[x][y];
    }
}

코드 구현 - 파이썬

n, m = map(int, input().split())
board = [list(input().strip()) for i in range(n)]
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
mem = [[-1] * m for _ in range(n)]
visit = [[False] * m for _ in range(n)]
flag = False

def dfs(x, y):
    global flag

    if flag:
        return 0

    if mem[x][y] != -1:
        return mem[x][y]

    visit[x][y] = True
    mem[x][y] = 1
    num = int(board[x][y])

    for i in range(4):
        nx = x + (dx[i] * num)
        ny = y + (dy[i] * num)

        if nx < 0 or ny < 0 or nx >= n or ny >= m or board[nx][ny] == 'H':
            continue

        if visit[nx][ny]:
            flag = True
            return 0

        mem[x][y] = max(mem[x][y], dfs(nx, ny) + 1)

    visit[x][y] = False
    return mem[x][y]

dfs(0, 0)

print(-1 if flag else mem[0][0])