[11회차]

Programmers Level.2 땅따먹기

def solution(land):
    dP = [[0,0,0,0] for _ in range(len(land))]
    dP[0] = land[0]
    for i in range(1, len(land)):
        for j in range(4):
            for k in range(4):
                if j != k:
                    dP[i][j] = max(dP[i-1][k], dP[i][j])
            dP[i][j] += land[i][j]
    answer = max(dP[len(land) - 1])
    return answer

 - DP 문제.

 

 

Programmers Level.2 삼각 달팽이

def solution(n):
    answer = []
    graph = [[0] * i for i in range(1, n + 1)]
    num = 1
    r = -1
    c = 0
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0:
                r += 1
            if i % 3 == 1:
                c += 1
            if i % 3 == 2:
                r -= 1
                c -= 1
            graph[r][c] = num
            num += 1
    for i in graph:
        for j in i:
            answer.append(j)
    return answer

 

 

Programmers Level.3 가장 먼 노드

from collections import deque


def solution(n, edge):
    graph = [[] for _ in range(n + 1)]
    distance = [0] * (n + 1)
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    q = deque()
    q.append(1)
    while q:
        node = q.popleft()
        for i in graph[node]:
            if distance[i] == 0:
                distance[i] = distance[node] + 1
                q.append(i)
    distance[1] = 0
    answer = [i for i in distance if i == max(distance)]
    return len(answer)

 - BFS 문제

 

 

Programmers Level.3 네트워크

def dfs(node, visited, computers):
    if not visited[node]:
        visited[node] = True
        for i in range(len(computers)):
            if computers[node][i] == 1:
                dfs(i, visited, computers)
        return True
    return False


def solution(n, computers):
    answer = 0
    visited = [False] * (n)
    for i in range(n):
        if dfs(i, visited, computers):
            answer += 1
    return answer

 - DFS 문제

 - 재귀함수 대신 stack으로 구현한 풀이가 있길래 공부해봤다.

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer