[python code review] 3주차(여행경로, DFS와 BFS, 토마토)

1. 여행경로 (중상)

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

코딩테스트 연습 - 여행경로

[dfs를 이용한 풀이]

from collections import defaultdict

def dfs(start):
    global routes
    stack = [start]
    path = []
    while stack:
        top = stack[-1]
        if not routes[top]:
            path.append(stack.pop())
        else:
            stack.append(routes[top].pop(0))

    return path[::-1]

def solution(tickets):
    global routes
    routes = defaultdict(list)
    for a, b in sorted(tickets):
        routes[a].append(b)
    result = dfs('ICN')
    return result

[dfs를 이용한 다른 풀이 ]

from collections import defaultdict


def dfs(node):
    global routes, answer
    # 딕셔너리에 값이 없으면 
    if not routes[node]:
        return node
    while routes[node]:
        nextNode = routes[node].pop(0)
        answer.append(dfs(nextNode))
    # 현재 노드에서 갈 수 있는 경로가 없으면    
    return node


def solution(tickets):
    global routes, answer
    answer = []
    routes = defaultdict(list)
    for a,b in sorted(tickets):
        routes[a].append(b)
    dfs('ICN')
    answer.append('ICN')
    return answer[::-1]

dfs('ICN')
answer.append('ICN')을

answer.append(dfs('ICN')) 와 같이 처리 가능 

 

[틀린 풀이]

from collections import deque

def bfs(start):
    global dic, answer
    que = deque([start])
    answer.append(start)
    while que:
        now = que.popleft()
        if now not in dic.keys() or not dic[now]:
            break
        # 알파벳 순으로 정렬
        for nextNode in sorted(dic[now]):
            answer.append(nextNode)
            que.append(nextNode)
            dic[now].remove(nextNode)
            break

def solution(tickets):
    global dic, answer
    answer = []
    dic = {}
    for ticket in tickets:
        a, b = ticket
        if a in dic.keys():
            dic[a].append(b)
        else:
            dic[a] = [b]
    # print(dic)
    # 방문했던 곳은 다시 방문하지 않도록...
    bfs('ICN')

    return answer

더이상 들어갈 곳이 없을 때까지 깊게 탐색하도록 dfs를 쓰는게 더 적절한 접근법이었다. 

반례 )  [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"]]

          ["ICN", "BBB"]부터 가야 모두 방문 가능

          위 코드는 무조건 알파벳 순서가 앞서는 경로를 선택하므로 항공권을 모두 사용할 수 없다. 

2. DFS와 BFS (중하)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

[풀이]

from collections import deque
# 정점, 간선, 시작 노드
n, m, s = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b); graph[b].append(a)
for g in graph:
    g.sort()
visited = [False for _ in range(n+1)]

# bfs
def bfs(i):
    visited = [False for _ in range(n + 1)]
    que = deque([i])
    visited[i] = True
    while que:
        node = que.popleft()
        print(node, end=' ')
        for nextNode in graph[node]:
            if not visited[nextNode]:
                que.append(nextNode)
                visited[nextNode] = True
# dfs
def dfs(i):
    visited[i] = True
    print(i, end=' ')
    for node in graph[i]:
        if not visited[node]:
            dfs(node)

dfs(s)
print()
bfs(s)

3. 토마토 (중상)

https://www.acmicpc.net/problem/7576 

7576번: 토마토

[풀이]

from collections import deque
move = [(1,0), (0,1), (-1,0), (0,-1)]

def bfs(tomato):
    time = 0
    deq = deque(tomato)
    while deq:
        x, y, t = deq.popleft()
        time = t
        for dx, dy in move:
            nx, ny = dx + x, dy + y
            if 0 <= nx < n and 0 <= ny < m:
                # 토마토가 아직 익지 않았다면
                if box[nx][ny] == 0:
                    # 토마토를 익혀라!!
                    box[nx][ny] = 1
                    deq.append((nx, ny, t+1))
    return time

m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]
result = 0
already = []
for i in range(n):
    for j in range(m):
        # 익은 토마토의 위치 저장하기
        if box[i][j] == 1:
            already.append((i, j, 0))
result = bfs(already)
# 익지 않은 토마토가 있다면 -1 리턴
for i in range(n):
    if 0 in box[i]:
        result = -1
        break
print(result)

[틀린 풀이]

from collections import deque
move = [(1,0), (0,1), (-1,0), (0,-1)]

def bfs(x, y):
    time = 0
    que = deque([(x, y, time)])
    while que:
        x, y, t = que.popleft()
        time = t
        for dx, dy in move:
            nx, ny = dx + x, dy + y
            if 0 <= nx < n and 0 <= ny < m:
                # 토마토가 아직 익지 않았다면
                if tomato[nx][ny] == 0:
                    # 토마토를 익혀라!!
                    tomato[nx][ny] = 1
                    que.append((nx, ny, t+1))
    return time


m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]

result = 0
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            result = max(result, bfs(i, j))

check = False
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            result = -1
            check = not check
            break
    if check:
        break
print(result)

테스트 케이스 3번같은 문제에 대해서 문제 발생

양쪽에서 접근해오는 '1'

과연 어떻게 처리해야 할까...? 

아이디어) + 1의 위치를 먼저 따로 저장하여 저장하여 접근해보자 -> 성공

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1