0912_algorithm_13565_침투

문제 : https://www.acmicpc.net/problem/13565

초기 구상과정

1. DFS 문제
2. dir 4가지로
   dc = [1, 0, -1, 0]
   dr = [0, 1, 0, -1]
3. 종료조건 : row == M - 1
4. visited list생성해서 이용하기

초기코드

M, N = map(int, input().split())
nodes = [list(map(int, list(input()))) for _ in range(M)]

def dect(row, col):
    global result
    dc = [1, 0, -1, 0]
    dr = [0, 1, 0, -1]
    if row == M - 1:
        result = 'YES'
        return
    else:
        for dir in range(4):
            if 0 <= row + dr[dir] < M and 0 <= col + dc[dir] < N and nodes[row + dr[dir]][col + dc[dir]] == 0 and visited[row + dr[dir]][col + dc[dir]] == 0:
                visited[row + dr[dir]][col + dc[dir]] = 1
                dect(row + dr[dir], col + dc[dir])

result = 'NO'
cols = []
visited = [[0] * N for _ in range(M)]
for i in range(N):
    if nodes[0][i] == '0':
        cols.append(i)

for col in cols:
    dect(0, col)

print(result)

수업시간에 풀었던 내용과 비슷해서 생각보다 전반적인 틀을 작성하는 시간은 얼마 안걸렸다. 서서히 DFS, Backtracking에 익숙해지고 있다고 생각했다. 격자에서 상하좌우 탐색하는 것은 꽤나 익숙하고 list에서 index를 다루는 것은 대학시절부터 꽤나 많이 했으니 어렵지 않았다.
그러나, 제출헀더니 런타임에러...

런타임에러?

런타임에러(runtime error)라는 단어는 많이 들었는데 왜 생기는 걸까?
보통 코드를 실행하며 생기는 에러들을 묶어서 표현하는 것이라는 것임을 알았다. 초기코드를 제출했을 때 상세내용을 확인하니 RecursionError였다. 재귀호출이 제한된 양을 넘어서면 나타나는 에러였다. 해결방법은 DFS를 BFS로 수정하거나 제한을 내가 변경하면 된다. DFS를 공부하고 있어서 전자보다는 후자를 선택했다

import sys

sys.setrecursionlimit(10**6)

제한을 변경하는 코드는 위 코드를 사용하면 된다.
이 코드를 적용하고 제출했더니 다시 런타임 에러가 떴다.

이번엔 런타임에러(IndexError)

너무나도 익숙한 에러창이었다. 다만, 굉장히 부끄러웠다. 초보적인 실수이기 때문이다. Index를 잘 조정하고 찾아내는 것에 도가 텄다고 생각하고 있던 상태였기 때문에 많이 부끄러웠다. 원인은 visited 리스트였다.

visited = [[0] * M for _ in range(M)]

nodes 리스트와 같은 형태인 M by N 리스트를 만들어야하는데 M by M 리스트를 만들었다. 제출하기 전에 sample에서 확인이 가능하지 않았나?
당연히 확인할 수 있었지만 예제2만 넣어보고 에제1은 넣어보지 않았기 떄문에 확인하지 못했다. 이를 수정하고 제출하니 PASS

최종 코드

import sys

sys.stdin = open('김병완_13565_침투.txt', 'r')

sys.setrecursionlimit(10 ** 6)

M, N = map(int, input().split())
# nodes = [list(map(int, list(input()))) for _ in range(M)]
nodes = [list(input()) for _ in range(M)]

def dect(row, col):
    global result
    dc = [1, 0, -1, 0]
    dr = [0, 1, 0, -1]
    if row == M - 1:
        result = 'YES'
        return
    else:
        for dir in range(4):
            # if 0 <= row + dr[dir] < M and 0 <= col + dc[dir] < N and nodes[row + dr[dir]][col + dc[dir]] == 0 and visited[row + dr[dir]][col + dc[dir]] == 0:
            if 0 <= row + dr[dir] < M and 0 <= col + dc[dir] < N and nodes[row + dr[dir]][col + dc[dir]] == '0' and visited[row + dr[dir]][col + dc[dir]] == 0:
                visited[row + dr[dir]][col + dc[dir]] = 1
                dect(row + dr[dir], col + dc[dir])

result = 'NO'
cols = []
visited = [[0] * N for _ in range(M)]
for i in range(N):
    if nodes[0][i] == '0':
        cols.append(i)

for col in cols:
    dect(0, col)
    
print(result)

이번에도 문제는 실행시간.. 굉장히 오래걸린다.. 걸려도 너무 오래 걸린다.. DFS의 문제인지 내 코드의 문제인지(솔직히 후자가 더 가능성이 큰 것 같다)는 모르겠지만 앞으로 더 공부해서 실행시간을 줄일 수 있는 방법들을 더 찾아봐야겠다.(Backtracking을 더 넣어야할까?)