[백준 BOJ] 1194 달이 차오른다, 가자. (python)

문제 링크 : https://www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

첫 문제 풀이입니다.

제목의 노래를 아신다면 문제가 재밌으니 꼼꼼히 읽어보시기 바랍니다.

정말 대표적인 DFS, 시뮬레이션 문제라고 생각합니다.

시간 제한과 제약 조건이 넉넉하니 구현만 잘하신다면 충분히 풀만한 문제라고 생각합니다.

 

DFS

기본적으로 python에서 DFS를 사용하신다면 collections의 deque를 사용하시면 좋습니다.

deQueue 과정에서 pop(0) 대신 deque의 popleft()를 써주는 것으로 DFS 시간을 많이 줄일수 있습니다.

나중에 기본적인 알고리즘 설명을 정리하는 글도 올려야겠네요..

만약 여러 자료구조를 연습해보고 싶으시다면 아래 tony9402님의 알고리즘 문제집중 Data Structure 문제집을 풀어보시면 좋습니다.

https://github.com/tony9402/baekjoon/tree/main/data_structure

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

시작 위치부터 네 방향을 도는 기본적인 DFS 과정을 따르며 가는 방향이 벽이나 잠긴 문이 아니라면 이동해주고, 열쇠라면 열쇠를 획득하는 행동을 해줍니다.

 

열쇠

열쇠를 획득했다면 저장해 주어야겠죠!

저는 단순히 열쇠를 획득했다면 해당 열쇠에 대한 값을 0에서 1로 바꾸어주었습니다.

문제 분류에 비트마스킹이 있었는데 열쇠 습득에 대한 값에 활용하는 것도 좋은 방법일것 같습니다.

 

방문

저는 DFS 탐색 문제에서 중복 방문을 방지하기위해 visited를 만들어 활용합니다.

이 문제에서는 열쇠를 가지고 있는지 아닌지가 다르므로 단순히 방문을 했다고 해서 다시 방문되는 것을 막을 수는 없습니다.

저는 visited에 열쇠 정보를 넣어주는 것으로 해결해보았습니다.

기존에 방문했던 경우들과 비교했을 때 새로운 열쇠를 습득한 경우에는 재방문을 허용하고 visited에 그 정보를 추가적으로 넣어주었습니다.

 

첫 문제풀이라 말할 것은 많은데 조리있게 말을 못한것 같습니다.

앞으로 더 좋은 풀이 이어가보겠습니다.

감사합니다.

 

from collections import deque

N, M = map(int, input().split())
maze = []
visited = [[[] for _ in range(M)] for _ in range(N)]
for n in range(N):
    line = input()
    maze.append(line)
    m = line.find('0')
    if m != -1:
        start = (0, n, m, 0, 0, 0, 0, 0, 0)
        visited[n][m].append((0, 0, 0, 0, 0, 0, 0))
now = deque()
now.append(start)
go = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = -1
while now:
    if ans != -1:
        break
    t, n, m, a, b ,c, d, e, f = now.popleft()
    t += 1
    for g_n, g_m in go:
        x = n + g_n
        y = m + g_m
        aa, bb, cc, dd, ee, ff = a, b, c, d, e, f
        if 0 <= x < N and 0 <= y < M:
            if maze[x][y] == '#':
                continue
            if maze[x][y] == 'a':
                aa = 1
            if maze[x][y] == 'b':
                bb = 1
            if maze[x][y] == 'c':
                cc = 1
            if maze[x][y] == 'd':
                dd = 1
            if maze[x][y] == 'e':
                ee = 1
            if maze[x][y] == 'f':
                ff = 1 
            if maze[x][y] == 'A' and not a:
                continue
            if maze[x][y] == 'B' and not b:
                continue
            if maze[x][y] == 'C' and not c:
                continue
            if maze[x][y] == 'D' and not d:
                continue
            if maze[x][y] == 'E' and not e:
                continue
            if maze[x][y] == 'F' and not f:
                continue
            if maze[x][y] == '1':
                ans = t
                break
            for v in visited[x][y]:
                if v[0] <= t and v[1] >= a and v[2] >= b and v[3] >= c and v[4] >= d and v[5] >= e and v[6] >= f:
                    break
            else:
                visited[x][y].append((t, aa, bb, cc, dd, ee, ff))
                now.append((t, x, y, aa, bb, cc, dd, ee, ff))
print(ans)