[BOJ 백준] 게임(1103) C++

링크 : https://www.acmicpc.net/problem/1103

1103번: 게임

 

문제 설명 : 

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

 

입력 : 

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

 

출력 : 

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

예제 입력 : 

3 7

3942178

1234567

9123532

 

예제 출력 : 

5

 

접근법 : 

1) 어떻게 풀 것인가?

지도에서 이동할 수 있는 최대 횟수를 구해야한다. 기본적으로 완전탐색 형태로 다 해보면 구할 수 있다.

그러나 50*50 맵에서 완전탐색을 할 경우 시간초과가 발생할 수 있다.

왜냐면 이론상 worst case로 2500!에 가까운 경우의 수가 발생할 수 있기 때문이다.

 

여러 조건으로 가지치기가 될 경우에도 삼성 A형 소검 기준으로 50*50 맵 크기는 BFS, DFS (DFS는 경우에 따라 함수 Stack Overflow 발생 가능)의 거의 마지노선이다.

 

Ex> 치킨배달 (백준 15686, https://www.acmicpc.net/problem/15686) 처럼 특정 노드들 간의 경우를 구한다거나

      탈출 (백준 3055, 문제 - https://www.acmicpc.net/problem/3055, 풀이 - https://subbak2.tistory.com/4)

      처럼 2배로 지도가 줄어드는 경우 

 

따라서 단순 완전탐색 조건으로는 성능상 무리가 있다. 그래서 단순 BFS, DFS 보단 간단한 형태의 DP 등을 접목해서

메모이제이션을 통해 메모를 하고 비효율적인 경우의 수를 줄여야한다. 

 

같은 개념이지만 DP 보다는 캐싱(caching)을 떠올리는게 이해하기 쉽다. 안 가도 되는 경우

(같은 좌표에 더 많은 count로 방문한 이력을 남겨서, 더 적은 count로 같은 좌표를 방문하면 가지치기로 방문하지 않기)를 잘 잘라내는게 문제의 핵심 조건이다.

 

이 경우 BFS+DP는 가능은 하겠지만 백트래킹이 매우 까다로워 DFS+DP를 추천.

 

 

2) 시간복잡도

전체 Node 개수가 2,500개 (50*50)이고 각 Node에서 이동가능한 좌표의 개수가 2,500개이므로,

정말 최악의 경우 1로 채워진 50*50 맵이 있다고 가정했을때 상황에 따라 2499!에 가까운 경우의 수가 발생할 수 있다.

최초에 2499개의 node 방문 가능 -> 2498개 가능...

 

물론 지도 범위 등으로 가지치기 등이 기본적으로 가능하지만 구멍과 무한LOOP 체크 외에는 특별한 가지치기가 불가능해 단순 BFS, DFS시 불가능하다. -> 실제 테스트시 시간초과 발생

 

C++ 기준 0ms

 

그러나 DFS+DP 처리할 경우 한 번 왔던 길은 다시 가지 않으므로 최종 실행시간은 Java 기준 100ms가 소요됐다.

 

 

3) 공간복잡도

50*50 int 배열 몇개(지도, 방문이력, DP)로 충분하다. 4Bytes * 50*50*3 = 약 30KBytes

 

 

4) 풀면서 놓쳤던점

- 처음에 백트래킹을 고려하지않은 BFS로 풀어서 시간초과가 발생했다.

 → visit배열을 작성하지 않은 문제점이 있었고 백트래킹이 상대적으로 쉬운 DFS로 방향 변경 + DP로 성능 이슈 해결. 완전탐색으로는 성능 문제가 있어 가지치기가 필요하고 DP 배열을 통해 경우의 수를 줄여야 통과가 가능하다.

 

- (Java) 무한LOOP에 빠질 경우 bw.write(-1); 로 작성해 답을 틀렸다. bw.write(String.valueOf(-1));로 수정했다.

  BufferedWriter를 사용할 경우 반드시 String 형태로 변환해줘야한다.

 

 

5) 이 문제를 통해 얻어갈 것

삼성 SW역량테스트 A형(Advanced)에 충분히 출제될 수 있는 난이도.

BFS, DFS로 문제를 어느정도 풀어봤다면 DP를 접목해서 입문하기 좋은 문제.

 

특정 알고리즘으로 접근한다는 생각보다 어떻게 하면 DFS에서 경우의 수를 줄일 수 있을까라는 생각을 하면 다른 문제를 푸는데도 도움될 것 같다.

 

C++ 코드 : 

// 게임 1103 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

#define MAX (52)

using namespace std;

int N,M;						// N : 보드 세로 크기, M : 보드 가로 크기
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int ans;						// ans : 정답

int map[MAX][MAX];				// 보드 입력값
int cache[MAX][MAX];			// 가지치기를 위한 지도
bool visit[MAX][MAX];			// 무한루프 확인을 위한 visit 배열

bool isInfinite;				// 무한루프인지 확인

void input();
void dfs(int r, int c, int cnt);

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	input();
	
	// 2. dfs를 수행한다
	visit[1][1] = true;
	dfs(1, 1, 1);

	// 3. 답을 출력한다.
	if (isInfinite) {
		printf("%d", -1);
	}
	else {
		printf("%d", ans);
	}
}

void input() {
	scanf("%d %d", &N, &M);
	// cin >> N>> M;
	char inputString[MAX];
	for (int i = 1; i <= N; i++) {
		scanf("%s", inputString);
		for (int j = 0; j < M; j++) {
			if (inputString[j] == 'H') {
				map[i][j + 1] = -1;
			}
			else {
				map[i][j + 1] = inputString[j]-'0';
			}
		}
	}
}

void dfs(int r, int c, int cnt) {

	// 답 최신화
	if (cnt > ans) {
		ans = cnt;
	}

	// 현재 위치 최고 값 기록
	cache[r][c] = cnt;

	// 네 방향으로 dfs 진행
	for (int i = 0; i < 4; i++) {
		int num = map[r][c];
		int nr = num * dr[i] + r;
		int nc = num * dc[i] + c;
		
		// 갈 수 없는 경우 가지 않음
		if (nr < 1 || nc < 1 || nr > N || nc > M
			|| map[nr][nc] == -1) {
			continue;
		}

		// 방문한 지점으로 돌아올 경우 무한 loop 가능
		if (visit[nr][nc]) {
			isInfinite = true;
			return;
		}

		if (cache[nr][nc] > cnt) continue;

		visit[nr][nc] = true;
		dfs(nr, nc, cnt + 1);
		visit[nr][nc] = false;

	}

}
#endif