[python code review] 11주차 (경주로 건설, 양과 늑대, 광고 삽입)

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

[BFS + 3차원 배열]

방향에 따라 건설비용을 따로 저장할 수 있도록 visited 배열을 3차원 배열로 처리해야 한다.

추천 문제 > https://www.acmicpc.net/problem/2206

from collections import deque


def solution(board):
    answer = 1e9
    n = len(board)
    move = [(-1,0),(1,0),(0,-1),(0,1)] # 위, 아래, 좌, 우
    visited = [[[1e9]*n for _ in range(n)] for _ in range(4)]
    deq = deque() # x, y, 방향, 비용
    
    # visited[0][0] = 0
    for i in range(4):
        visited[i][0][0] = 0 # 초기화
        
    if board[0][1] == 0: # 원점기준 아래 좌표
        deq.append((0, 1, 3, 100))
        visited[3][0][1] = 100
    if board[1][0] == 0: # 원점기준 오른쪽 좌표
        deq.append((1, 0, 1, 100))
        visited[1][1][0] = 100

    # print(deq)
    while deq:
        x, y, d, c = deq.popleft()
        
        if x == n-1 and y == n-1:
            answer = min(answer, visited[d][x][y])

        for i in range(4):
            nx, ny, nd = x + move[i][0], y + move[i][1], i

            if 0 <= nx < n and 0 <= ny < n:
                if board[nx][ny]:
                    continue

                cost = c + 100 if nd == d else c + 600

                if visited[nd][nx][ny] > cost:
                    deq.append((nx, ny, nd, cost))
                    visited[nd][nx][ny] = cost
                    
    return answer

 

[tc 25번에서 실패한 코드]

맞왜틀? 하면서 질문글을 보니 아래와 같은 반례가 있었다.

[[0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 1, 1, 1, 0], [1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 0]]
(output : 4900, answer : 4500)

from collections import deque


def solution(board):
    answer = 1e9
    n = len(board)
    move = [(-1,0),(1,0),(0,-1),(0,1)] # 위, 아래, 좌, 우
    visited = [[1e9]*n for _ in range(n)]
    deq = deque() # x, y, 방향, 비용
    visited[0][0] = 0

        
    if board[0][1] == 0:
        deq.append((0, 1, 3, 100))
        visited[0][1] = 100
    if board[1][0] == 0:
        deq.append((1, 0, 1, 100))
        visited[1][0] = 100

    # print(deq)
    while deq:
        x, y, d, c = deq.popleft()
        
        if x == n-1 and y == n-1:
            answer = min(answer, visited[x][y])

        for i in range(4):
            nx, ny, nd = x + move[i][0], y + move[i][1], i

            if 0 <= nx < n and 0 <= ny < n:
                if board[nx][ny]:
                    continue

                cost = c + 100 if nd == d else c + 600

                if visited[nx][ny] >= cost:
                    deq.append((nx, ny, nd, cost))
                    visited[nx][ny] = cost
                    
    return answer

 

 

https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

[backtracking]

비트마스킹을 사용하여 방문 처리하는 것이 효율적이라고 한다. 

from collections import defaultdict

answer = 0
def DFS(graph, visited, info, sheep, wolf):
    global answer
    
    answer = max(answer, sheep)
    # 양보다 늑대가 더 많거나 같다면
    if sheep <= wolf:
        return
    for i in range(len(visited)):
        # 해당 노드에 방문한 경우
        if visited[i]:
            for e in graph[i]:
                # 자식 노드를 아직 방문하지 않았다면
                if not visited[e]:
                    # 자식 노드 방문처리
                    visited[e] = 1
                    # 늑대가 있다면
                    if info[e] == 1:
                        DFS(graph, visited, info, sheep, wolf+1)
                        visited[e] = 0
                    # 양이 있다면 
                    else:
                        DFS(graph, visited, info, sheep+1, wolf)
                        visited[e] = 0
                    
def solution(info, edges):
    graph = defaultdict(list)
    
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
        
    v = [0]*len(info)
    v[0] = 1 # 루트 노드에는 항상 양이 있음
    DFS(graph, v, info, 1, 0)
    return answer

 

[BFS]

from collections import deque


def solution(info, edges):
    answer = 0
    G = {}
    for i in range(len(info)):
        G[i] = []

    for src, dst in edges:
        G[src].append(dst)

    q = deque([[[0], 1, 0]]) # [node, sheep, wolf]
    while q:
        nodes, sheep, wolf = q.popleft()
        answer = max(answer, sheep)
        # 현재 방문한 노드들
        node_set = {node:1 for node in nodes}
        
        for node in nodes:
            for nxt in G[node]:
                n_sheep, n_wolf = sheep, wolf
                # 아직 방문하지 않는 노드라면 
                if not node_set.get(nxt, 0):
                    # 양일 경우
                    if info[nxt] == 0:
                        n_sheep += 1
                    # 늑대일 경우
                    else:
                        n_wolf += 1
                    # 늑대보다 양이 많다면 
                    if n_sheep > n_wolf:
                        q.append([nodes + [nxt], n_sheep, n_wolf])


    return answer

 

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

[문자열 + 메모이제이션]

참고하기 좋은 블로그 : https://dev-note-97.tistory.com/156

def to_hour(time):
    h = time // 3600
    # h = '0' + str(time) if time < 10 else str(time)
    time = time % 3600
    m = time // 60
    time = time % 60
    s = time
    return "%02d:%02d:%02d"%(h, m, s)

def str_to_int(time):
    h, m, s = time.split(':')
    return int(h)*3600 + int(m)*60 + int(s)


def solution(play_time, adv_time, logs):

    play_time = str_to_int(play_time)
    adv_time = str_to_int(adv_time)
    all_time = [0 for i in range(play_time +1)]
    
    for log in logs:
        start, end = log.split('-')
        
        start = str_to_int(start)
        end = str_to_int(end)
        
        all_time[start] += 1
        all_time[end] -= 1
    # 구간별 시청자수 기록
    for i in range(1, len(all_time)):
        all_time[i] = all_time[i] + all_time[i-1]
    # 모든 구간 시청자 누적 기록     
    for i in range(1, len(all_time)):
        all_time[i] = all_time[i] + all_time[i-1]
        
    most_view = 0
    max_time = 0
    
    for i in range(adv_time-1, play_time):
        if i >= adv_time:
        	# 누적된 시청자수를 바탕으로 가장 시청자수가 많은 구간 탐색 
            if most_view < all_time[i] - all_time[i - adv_time]:
                most_view = all_time[i] - all_time[i - adv_time] 
                max_time = i - adv_time + 1
        else:
            if most_view < all_time[i]:
                most_view = all_time[i]
                max_time = i - adv_time + 1
    
    return to_hour(max_time)