게임 맵 최단거리

🤡게임 맵 최단거리 (Lv.2)

🤑풀이

from collections import deque

def solution(maps):
    maps[0][0] += 1
    queue = deque([(0, 0, 1)])
    steps = [(1,0), (0, -1), (0, 1), (-1, 0)]   # R, D, U, L
    while len(queue) > 0 :
        pop = queue.popleft()
        for step in steps :
            dr = pop[0] + step[0]
            dc = pop[1] + step[1]
            if dr >= 0 and dr < len(maps) and dc >= 0 and dc < len(maps[0]) and maps[dr][dc] == 1 :
                if dr== len(maps)-1 and dc == len(maps[0])-1 :
                    return pop[2] +1
                else :
                    maps[dr][dc] += 1
                    queue.append((dr, dc, pop[2]+1))
            
    return -1

👩‍🏫 아이디어

• BFS(너비 우선 탐색)을 최단거리 이동경로를 찾는 관점으로 실행.

네트워크

🤡네트워크 (Lv.3)

🤑풀이

import numpy as np

def dfs(start, computers) :
    for j in range(len(computers)) :
        if computers[start][j] == 1 :
            computers[start][j] = 0
            next_s = j
            dfs(next_s, computers)

def solution(n, computers):
    L = len(computers)
    answer = 0
    while np.sum(computers) > 0 :
        start = 0
        # search start
        for i in range(L) :
            if computers[i][i] == 1 :
                start = i
                break
        computers[start][start] = 0
        dfs(start, computers)
        answer += 1
    return answer

👩‍🏫 아이디어

• 다음 과정의 반복

  • 시작점 탐색 : 탐색되지 않은(네트워크를 연결시키지 않은) 시작점 탐색.
  • 작업 : 각 지점에서 DFS를 수행하여 네트워크 연결.

• 각 네트워크를 끝까지 연결시키는게 중요. 따라서, BFS가 아닌 DFS를 사용.

단어 변환

🤡단어 변환 (Lv.3)

🤑풀이

from collections import deque

# 인접 행렬 Adjacent Matrix 생성
def get_adjacent_matrix(words, word2idx, idx2word) :
    adjacent_matrix = [[1 for _ in range(len(words))] for _ in range(len(words))]
    for i in range(len(words)) :
        for j in range(len(words)) :
            # 한글자만 다른지 확인
            diff = 0
            for k in range(len(words[0])) :
                if idx2word[i][k] != idx2word[j][k] :
                    diff +=1
                    if diff > 1 :
                        adjacent_matrix[i][j] = 0
                        break   
    return adjacent_matrix
    
    
def solution(begin, target, words) :
	# word2idx, idx2word dictionary 생성
    word2idx = {s : i+1 for i, s in enumerate(words)}
    idx2word = {i+1 : s for i, s in enumerate(words)}
    word2idx[begin],idx2word[0]  = 0, begin
    words.append(begin)
    adjacent_matrix = get_adjacent_matrix(words, word2idx, idx2word)
    
    # Queue
    queue = deque([(word2idx[begin], 0)])
    
    while len(queue) > 0 :
        i, cnt = queue.popleft()

        for j in range(len(adjacent_matrix[i])) :
            if adjacent_matrix[i][j] == 1 :
                if idx2word[j] == target :
                    return cnt + 1
                queue.append((j, cnt+1))
                adjacent_matrix[i][j] = 0
    return 0

👩‍🏫 아이디어

• idx2word, word2idx dictionary 생성
  • list로 접근하기 위해 단어를 index화 함.
• 최단 거리이므로 BFS의 알고리즘을 최단 경로 탐색에 사용.
  • 최단 경로 탐색과 너비 우선 탐색은 엄연히 다름.
  • 하지만, "최단 경로를 찾아라"문제에 대해서는 두 탐색과정이 동일한 정답을 내 놓는다. 따라서, 최단 거리 문제는 BFS문제로 풀이.