[백준3055] 탈출

문제

---

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

3055번: 탈출

 

생각의 흐름

---

정말 너무 미운 문제다...ㅜㅜ 이거때문에 코딩 그만둘까 생각함... 진짜 꿈에서도 이 문제 푸는 꿈 꾼 듯...정답률이 20%대이니 그럴만도 하다. 이 문제가 어려운 이유는 BFS를 두 번 사용하여야 하고 그들 간의 상관관계를 시간의 흐름에 따라 잘 분석해야 하기 때문이다. 결국 며칠을 고민하다 다른 블로그의 정답을 참고하였다. 대신 코드에 대한 분석을 자세히 하려고 한다.

먼저 요약하자면 S에서 D지점까지 가는 최단 경로를 구하는 문제이다. 이 때, 물이 먼저 인접한 영역을 덮치도록하고(water에 대한 BFS call) S가 인전한 영역을 이동(dudu에 대한 BFS call)하도록 한다. 이는 물이 덮칠 예정인 곳으로 S가 이동하지 못한다는 문제의 조건을 반영하기 위함이다.

내가 어려움을 겪었던 또 다른 부분은 KAKTUS를 출력해야 하는 경우, 다시말해 S가 D로 이동하는 것이 불가능한 경우를 판별하는 것이다. 이 부분은 사실 아주 간단한 방법으로 해결이 가능한데 count라는 변수를 N*M으로 초기화한 후에 while문을 돌 때마다 1씩 빼준다. 그리고 while문의 종료조건은 S가 D로 이동했을 때 up시켜준 flag(stop변수)를 이용한다. 그럼 도달하지 못하는 경우는 while문이 계속해서 돌아가고 결국 count가 음수가 되버린다. 이 때 KAKTUS를 출력하도록 하면 된다.

 

깨달은 점

---

1. board라는 리스트에 input으로 주어진 원래의 정보를 저장하고 매 싸이클마다 갱신되는 정보(이 문제의 경우 해당 칸까지 가기 위한 최소 시간)를 record라는 새로운 리스트에 기록한다. 나의 경우 처음에 board에 갱신된 정보까지 기록을 하려다 보니 정보가 섞여 어려움이 있었다. 항상 기존의 정보는 그대로 두되 새로운 변수에 갱신되는 정보를 쓰도록 하자!
2. 각 단계를 나타낼 수 있는 flag(아래의 코드에서 SET, stop, count)를 적절히 사용하자! 이것은 각 단계를 나타내면서 후에 반복문의 종료조건을 알려주는 강력한 정보가 된다. 그리고 main에서 작동되는 가장 큰 반복문(아래의 코드에서 while not stop)의 종료조건은 가장 핵심적이므로 언제 종료가 되어야 하는지를 잘 상정하고 해당 조건에 연결되는 flag 변수가 무엇인지를 잘 파악해야 한다.
3. 어려운 자료구조를 사용하려고 굳이 애쓰지 말자! 처음에 최소시간을 찾기 위해 priorityqueue를 import하여 사용하려고 하던 것이 문제를 더욱 어렵게 만들었다. 하지만 아래의 코드에서 보듯이 단순히 list만으로도 충분히 구현이 가능하다. 항상 문제는 가장 simple한 방법으로 복잡하지 않게 풀도록 하자!! "Simple is the best."

 

코드

---

# 출처 : https://jrc-park.tistory.com/33
dx = [0,1,0,-1]
dy = [-1,0,1,0]

def move(x,y):
    global stop
    SET = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if board[x][y] == '*':  # 물
                if  board[nx][ny] == '.'or board[nx][ny] == 'G':
                    board[nx][ny] = '*'

            # S-> D
            if board[x][y] == 'S':# 비버
                if board[nx][ny]=='.':  # 이동
                    SET =True
                    board[nx][ny] = 'S'
                    record[nx][ny] = record[x][y] + 1

                if board[nx][ny]=='D': # 종료
                    record[nx][ny] = record[x][y] + 1
                    stop = True
                    print(record[nx][ny])
                    break

    # 이동한 칸 표시
    if SET:
        board[x][y] = 'G'

M, N = map(int, input().split())
board = [list(input()) for _ in range(M)]
record = [[0]*N for i in range(M)]
stop = False
count = M*N
while not stop:
    # 매 싸이클마다 초기화되는 두 리스트
    water_lst = []
    dudu_lst = []
    for i in range(M):
        for j in range(N):
            if board[i][j]=='*':
                water_lst.append((i,j))

            if board[i][j]=='S':
                dudu_lst.append((i,j))

    for p in water_lst:
        move(p[0], p[1])

    for p in dudu_lst:
        move(p[0],p[1])
        if stop:
            break

    count -= 1
    if count <0:
        print('KAKTUS')
        break