[12회차]

Programmers Level.3 여행경로

def solution(tickets):
    routes = {}
    for start, end in tickets:
        if start not in routes:
            routes[start] = [end]
        else:
            routes[start].append(end)
            routes[start] = sorted(routes[start],reverse=True)
    stack = ['ICN']
    answer = []
    while stack:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            answer.append(stack.pop())
        else:
            stack.append(routes[top].pop())
    return answer[::-1]

 - DFS 문제. routes를 구현하는 것 까진 스스로 했는데, 테스트 케이스 1,2 에서 실패가 났다. 고민하다 결국 구글의 힘을 빌렸다...

 

 

Programmers Level.3 2xn타일링

def solution(n):
    answer = 0
    dP = [0] * (60001)
    dP[1] = 1
    dP[2] = 2
    if n <= 2:
        return dP[n]
    for i in range(3, n + 1):
        dP[i] = (dP[i-1] + dP[i-2]) % 1000000007
    return dP[n]

 - DP

 

 

Programmers Level.3 정수 삼각형

def solution(triangle):
    r = len(triangle)
    c = len(triangle[-1])
    dP = [0] * c
    for i in range(r):
        for j in range(i,-1,-1):
            if j == i:
                dP[j] = dP[j-1] + triangle[i][j]
            elif j == 0:
                dP[j] = dP[j] + triangle[i][j]
            else:
                dP[j] = max(dP[j-1],dP[j]) + triangle[i][j]
    return max(dP)

 - DP

 

 

Programmers Level.3 등굣길

def solution(m, n, puddles):
    dP = [[-1] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dP[i][0] = 0
    for i in range(n + 1):
        dP[0][i] = 0
    dP[1][1] = 1
    for a, b in puddles:
        dP[a][b] = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if (i == 1 and j == 1) or dP[i][j] == 0:
                continue
            dP[i][j] = dP[i-1][j] + dP[i][j-1] 
    return dP[m][n] % 1000000007

 - DP문제

 - 아래는 다른 사람의 풀이. 나는 물 웅덩이를 0으로 지나지 않은 길을 -1로 표현했는데 아래 풀이는 웅덩이를 -1로 지나지 않은 길을 0 으로 표현했다.

def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] 
    if puddles != [[]]:                   
        for a, b in puddles:
            grid[b][a] = -1                
    grid[1][1] = 1
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:              
                continue
            if grid[j][k] == -1:          
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007  

    return grid[n][m]

 

 

Programmers Level.3 단어 변환

from collections import deque

def check(x, word):
    cnt = 0
    for i in range(len(word)):
        if x[i] != word[i]:
            cnt += 1
    if cnt == 1:
        return True
    return False
    
    
def solution(begin, target, words):
    if target not in words:
        return 0
    q = deque()
    q.append([begin,[]]) # 현재 단어와 이미 방문한 단어
    while q:
        now, before = q.popleft()
        for word in words:
            if word not in before and check(word, now):
                if word == target:
                    return len(before) + 1
                a = before[:]
                a.append(word)
                q.append([word,a])
    return 0

 - BFS를 사용해야 한다는 생각은 할 수 있었지만 어떻게 구현해야하는지는 도저히 떠오르지 않아서 구글 검색으로 해결했다. DFS&BFS가 어떤 경우에 적용하는지는 알겠지만 구현하는 연습은 좀 더 해야 할 듯.