[프로그래머스 lv3] 등굣길 (bfs/dp/파이썬) 2/3

Try1. 장렬하게 실패

m = 0
n = 0
Cnt = 0

def dfs(x, y, Visit):
    dx = [0, 1] # 이전으로 되돌아가는 경우는 없음
    dy = [1, 0]
    global Cnt
    global puddles
    Visit[x][y] = True
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx==n-1 and ny==m-1: Cnt+=1
        if 0<=nx<n and 0<=ny<m and not Visit[nx][ny]:
            dfs(nx, ny, Visit)
            Visit[nx][ny]=False

def solution(_m, _n, puddle_list):
    global m
    global n
    global Cnt
    global puddles
    puddles = puddle_list
    m, n = _m, _n
    Visit = [[False for _ in range(m)] for _ in range(n)]
    for puddle in puddle_list:
        px, py = puddle
        Visit[px-1][py-1]=True
    dfs(0, 0, Visit)
    # print(Cnt)
    return Cnt

물론 테스트 코드는 잘 돌아갔다. 그런데 모든 정답을 장렬히 실패했다.
여전히 이 코드의 문제가 무엇인지는 잘 모르겠다.

Try2. 장렬한 두 번째 실패

그림을 그려보다 알았다. 역시 dp로 풀어야 했던 문제였다.
그래서 아래 코드를 돌려보았다.
(+ 10000007로 나눈 나머지를 저장하는 과정도 잊지 않았다)

m = 0
n = 0
Grid = []

def makedp():
    for i in range(n):
        for j in range(m):
            if i==0: Grid[i][j] = 1
            if j==0: Grid[i][j] = 1
            if i>0 and j>0 and Grid[i][j] != -1:
                if Grid[i-1][j] == -1: # 윗셀이 침수지역인 경우
                    Grid[i][j] = Grid[i][j-1]
                elif Grid[i][j-1] == -1: # 왼쪽셀이 침수지역인 경우
                    Grid[i][j] = Grid[i-1][j]
                else: Grid[i][j] = Grid[i-1][j] + Grid[i][j-1]

def solution(_m, _n, puddles):
    global m
    global n
    global Grid
    m, n = _m, _n
    Grid = [[0 for _ in range(m)] for _ in range(n)]
    for puddle in puddles:
        py, px = puddle
        Grid[px-1][py-1] = -1 # False로 표현하기는 너무 귀찮다. 전부 숫자로 만들자.
    # print(Grid)
    makedp()
    # print(Grid, Grid[n-1][m-1])
    return Grid[-1][-1]

Try3. 결국 다른 사람의 풀이를 참조함

def solution(m, n, puddles):
    puddles = [[q,p] for [p,q] in puddles]      # 미리 puddles 좌표 거꾸로
    dp = [[0] * (m + 1) for i in range(n + 1)]  # dp 초기화
    dp[1][1] = 1           # 집의 위치(시작위치)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1: continue 
            if [i, j] in puddles:    # 웅덩이 위치의 경우 값을 0으로
                dp[i][j] = 0
            else:                    # 현재 칸은 왼쪽 칸, 위 칸의 합산!
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    return dp[n][m]

훨씬 간단하다. 그리고 여기서 잘한 점은 일단 1) puddle의 xy 좌표가 반대로 되어있다는 것을 놓치지 않은 것.
2) 좌표열을 일관되게 바꾸려고 0으로 만든 것
3) 집 위치만 1로 두고 연산을 통일시킨 것 (0부터 시작하는 덕에 i-1이나 j-1의 연산을 낭비하지 않았다)

추가 Try2.5 DFS 코드 수정

m = 0
n = 0
Cnt = 0

def dfs(x, y, Visit):
    dx = [0, 1] # 이전으로 되돌아가는 경우는 없음
    dy = [1, 0]
    global Cnt
    global puddles
    Visit[x][y] = True
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx==n-1 and ny==m-1: Cnt+=1
        if 0<=nx<n and 0<=ny<m and not Visit[nx][ny]:
            dfs(nx, ny, Visit)
            Visit[nx][ny]=False

def solution(_m, _n, puddle_list):
    global m
    global n
    global Cnt
    global puddles
    puddles = puddle_list
    m, n = _m, _n
    Visit = [[False for _ in range(m)] for _ in range(n)]
    for puddle in puddle_list:
        py, px = puddle
        Visit[px-1][py-1]=True
    dfs(0, 0, Visit)
    # print(Cnt)
    return Cnt

puddles의 xy 좌표가 반대로 되어있다는걸 깨닫고 수정했다.
역시 내가 사랑하는 알고리즘 dfs다.

정답은 맞았지만, 싸그리 시간초과가 나버렸다.