1405

날짜 : 2023. 06. 25

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/1405

 

 

코드

import sys

def back(s, now):
    if len(s) == N:
        route.append(s)
        return
    r, c = now
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if not visited[nx][ny]:  # 겹치지 않은 경우
            visited[nx][ny] = True  # 방문처리
            back(s + dir[i], (nx, ny))  # 재귀
            visited[nx][ny] = False

t = list(map(int, sys.stdin.readline().split()))
N = t[0]
rate = dict()  # 방위별 확률
dir = ['E', 'W', 'S', 'N']  # 방향저장
route = list()  # 단순한 이동경로 저장
for i in range(1, 5): rate[dir[i-1]] = t[i] / 100

visited = [[False] * 30 for _ in range(30)]  # 방문체크
now = (15, 15)  # 현재위치
visited[15][15] = True

# 동, 서, 남, 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = 0
back("", (15, 15))
for s in route:
    t = 1
    for i in s:
        t *= rate[i]
    res += t
# print(route)
print(res)

 

 

풀이

- 조건에 따라 입력받은 후 백트래킹을 실행한다.

- 우선 동, 서, 남, 북 방향으로 이동이 가능하고, 각 방향마다 확률이 다르기 때문에 알기쉽게 해시를 사용해서 입력받는다.

- 또한 n값이 14라는 점에서 총 14만 이동하는 것을 알 수 있었기 때문에 방문체크(단순하지 않은 케이스)를 확인하기 위해 n의 2배 이상값인 30으로 전체 그래프를 설정하고, 그 그래프의 중간지점인 (15, 15)를 시작점으로 설정했다.

- 이후, 동, 서, 남, 북으로 DFS를 실행하면서 방문여부를 체크하고, 방문하지 않은 경우 방문체크 후 재귀를 실행, 리턴한 경우에는 다시 미방문처리를 한다.

- 재귀하면서 s + dir[i] 방식으로 경로를 기록하고 해당 경로의 길이가 n값과 동일한 경우(n번 이동) 경로를 담는 리스트(route)에 저장 후 리턴한다.

- 백트래킹을 전부 실행한 후에는 경로의 값들에 대하여 해시값을 사용해 아웃풋을 구한다.

 

알게된 점

- 맨 처음 시작점을 어떻게 해야할지를 고민했던 것 같다.

- (0, 0)으로 시작하면 분명 음수인 row와 column이 발생할 것이기 때문이다.

- 그래서 n값을 확인했고 최대 14라는 점에서 그냥 그래프를 미리 적당히 큰 크기로 정해버리고 중간지점에 던지는 방식으로 진행했다.

- 그 이후에는 전형적인 백트래킹 문제였기 때문에 크게 어려운 점은 없었다.

 

 

참고 사이트

-