허진혁

게임 맵 최단거리

접근방법

도착점이 접근할 수 없는 경우 -1을 리턴한다

방문확인용 visited를 만들고 좌표 이동을 위해 dx, dy를 만들어 둔다.

좌표 이동 조건을 좌표(그래프)의 범위를 벗어나지 않고, 1이라고 표시된 곳만 이동이 가능하다.

좌표를 이동하면서 이동할 때 마다 이동횟수를 표기하기 위해 시작점부터 이동할 떄마다 +1을 해주고 방문처리를 한다.

from collections import deque

def solution(maps):
    n = len(maps) # 세로
    m = len(maps[0]) # 가로
    
    if maps[n-1][m-2] == 0 and maps[n-2][m-1] == 0:
        return -1
    else:
        bfs(maps, n, m)
    return maps[n-1][m-1]


def bfs(maps, n, m):
    visited = [[False]*m for _ in range(n)]
    queue = deque()
    queue.append([0, 0])
    #  상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        y, x = queue.popleft()
        visited[y][x] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if maps[ny][nx] == 1:
                    if not visited[ny][nx]:
                        visited[ny][nx] == True
                        maps[ny][nx] = maps[y][x]+1
                        queue.append([ny, nx])

    return maps
Python
복사

# 게임 맵 최단거리
from collections import deque

def solution(maps):
    n = len(maps) # 세로
    m = len(maps[0]) # 가로
    
    answer = bfs(maps, n, m)
    if answer == 1:
        answer = -1
    return answer


def bfs(maps, n, m):
    visited = [[False]*m for _ in range(n)]
    queue = deque()
    queue.append([0, 0])
    #  상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        y, x = queue.popleft()
        visited[y][x] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if maps[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] == True
                    maps[ny][nx] = maps[y][x]+1
                    queue.append([ny, nx])
                    # print(f"maps[x][y]={maps[nx][ny]}")
    return maps[n-1][m-1]
Python
복사

실수한 부분

보통 이차원 배열은 list[행][열]이다. 하지만 행이 달라진다는 것은 세로줄이 바뀐다는 것. x, y보다는 나의 이해를 위해 y,x로 해두었다.

여행 경로

접근방법

tickets의 도착점들을 알파벳이 빠른 순으로 정렬을 한다.

첫 출발을 ICN을 고정한다.

[begin, dest]를 deque를 통해 그래프에 반복적으로 순회한다.

이전에 꺼내온 end와 순회하면서 꺼낸 begin이 일치하면 [begin, dest]를 deque에 넣는다.

answer에 dest를 넣고 한번의 순회를 끝낸다.

def solution(tickets):
    answer = []
    tickets.sort(key= lambda x:(x[1], x[0]))
    for i, [start, end] in enumerate(tickets):
        if start == "ICN":
            first, seocnd = tickets.pop(i)
            break

    queue = deque([])
    queue.append([first, seocnd])
    answer.append(first)
    answer.append(seocnd)
    while queue:
        print(queue)
        start, end = queue.popleft()
        for i, [begin, dest] in enumerate(tickets):
            if end == begin:
                b, d = tickets.pop(i)
                queue.append([b, d])
                answer.append(d)
                break
    return answer
Python
복사

문제점

1. "ICN" -> "BOO"

2. "ICN" -> "COO"

3. "COO" -> "ICN"

이러할 경우 ICN → Boo 로 끝나버려서 3번을 탐색하지 못한다 즉, 모든 도시를 방문하지 못할 경우도 생긴다. (ICN → COO → ICN → BOO)로 갈 방법을 찾아야 한다.

사용한 라이브러리

from collections import defaultdict

딕셔너리 value값의 타입을 미리 정해주는 역할

접근 방법

{시작 : [여러개의 도착]} 형태로 그래프를 만든다.

도착점들을 역순으로 정렬 (스택사용하기 위해)

알파벳이 빠른순 체크

항상 출발은 “ICN” 고정

스택이 빌 때 까지 모든 노드 깊이 탐색(한 노드의 끝까지 탐색하기 때문에 dfs)

스택에서 가장 상위의 값 pop한 것을 point에 넣음

그래프의 key값이 없거나, 그래프[key값]의 value값이 없으면 answer에 삽입

b의 조건이 아닌 경우 스택에 삽입

def solution(tickets):
    graph = defaultdict(list)
    for (start, end) in tickets:
        graph[start] += [end]
    
    # 역순
    for i in graph.keys():
        graph[i].sort(reverse=True)
    
    stack = ["ICN"]
    answer = []
    # print(graph)

    while stack:
        point = stack.pop()
        # 키 값에 없거나, 키값이 있는데 밸류값이 없을 때
        if point not in graph or len(graph[point]) == 0:
            answer.append(point)
        else:
            stack.append(point)
            stack.append(graph[point].pop())
    
    return answer[::-1]
Python
복사

생각지도 못했던것

defaultdict 라이브러리 사용하기. 그냥 딕셔너리 사용할 때, sort함수가 안됨.

출발점과 연결된 도착점들을 찾았을 때, 보통은 도착점을 찾자마자 answer 배열에 넣으려 했을거임. 그렇게 하다보니 스택 따로, 배열 따로 복잡해짐. 스택에 차곡차곡 넣고, 스택에서 빼서 배열에 넣는 것을 배웠음.