백준 1103. 게임

tose33 2022. 10. 8. 14:37

1103번: 게임

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

www.acmicpc.net

이 문제는 처음 봤을때는 그냥 dfs로 모든 경우 구하면 되는것 같지만 중복되는 연산이 많기 때문에 dp를 이용해야 한다.

dp[][] 배열과 mark[][] 배열을 만든다.

mark 배열은 방문한 적이 있다면 true로 해준다.

dp 배열은 해당 위치까지 오는데 동전을 움직인 최대 횟수를 기록한다.

dfs를 돌면서 다음 위치가 mark[][] == true 즉 이미 방문한적이 있다면 싸이클이 형성된다는 것이고 -1 을 출력하고 바로 프로그램을 종료하면 된다.

다음 위치의 dp[][]값이 -1이 아니고(방문한적이 있고) 현재 계산 깊이보다 크다면, 계산할 필요 없으므로 계산을 안해줘야 시간초과가 안난다.

이런 문제를 풀때마다 값을 리턴하는 dfs 를 내가 아직 서투르다고 느껴진다.

다른 분들 풀이를 참조해서 값을 리턴하는 dfs로 구현해봤다.