0717 yesterdayReview

0716 PS : 게임 맵 최단거리,위장

게임 맵 최단거리

단순한 BFS 문제였다.
간단한 BFS/DFS는 풀 수 있는데, 좀 꼬아놓으면 시간이 너무 오래걸려서 더 공부를 해야겠다...
욕심같이서는 다익스트라나 플로이드 같은 알고리즘 공부하고 싶은데, 왜 이렇게 머리에 안들어오는지 모르겠다...

#0715
#단순한 BFS 문제 
from collections import deque 

def solution(maps):
    answer = 0
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    r = len(maps)
    c = len(maps[0])
    
    graph = [[-1]*c for _ in range(r)]
    
    queue = deque()
    queue.append([0,0])
    graph[0][0] = 1
    
    while queue: 
        y,x = queue.popleft()
        
        #현재 위치에서 4가지 방향으로 확인
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if 0<= nx < c and 0<= ny < r and maps[ny][nx] ==1:
                if graph[ny][nx] == -1:
                    graph[ny][nx] = graph[y][x]+1
                    queue.append([ny,nx])
                    
    answer = graph[-1][-1]
    
    return answer

BFS 알고리즘

BFS란 루트노드에서 시작해서 인접한 노드를 탐색하는 너비우선 탐색알고리즘이다.
-두 노드 사이의 최단경로를 구할 때 사용
-자료구조 Queue를 사용 (*python에서는 deque)

구현 방법

1)탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다
2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다

from collections import deque

def bfs(graph,visited,start_node):
    queue = deque([start_node])
    # start node를 방문 처리한다. 
    visited[start_node] = True
    #큐가 빌 때 까지 반복한다. 
    
    while queue:
    	#큐에서 노드를 꺼낸다
        v = queue.popleft()
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

위장

이렇게 푸는게 맞는 건지..? 모르겠는 문제
코딩테스트용 문제를 풀다보면 뭔가 답만 나오고 맞기만 하면 되는거 같아서 내가 문제 푸는 방식이 잘못됐나 싶기도 하다
우선 Hash로 되어 있어서 dictionary를 이용해서 풀었는데, 경우의 수도 고민해야하는 문제 였다.. (경우의 수 어려워..)
dictionary는 손에 안익는 늬낌이라 열심히 공부해야겠다ㅏㅏ

def solution(clothes):
    answer = 1
    
    dic = {}
    
    for element in clothes:
        key = element[1] 
        value = element [0]
        if key in dic:
            dic[key].append(value)
        else:
            dic[key] = [value] 
    
    for i in dic:
        print(len(dic[i])+1)
        answer *= (len(dic[i])+1)
    
    return answer-1

Dictionary

딕셔너리 타입은 immutable한 키(key)와 mutable한 값(value)으로 맵핑되어 있는 순서가 없는 집합이다

*mutable은 값이 변한다는 뜻이고, immutable은 값이 변하지 않는다는 의미이다. 자료형마다 특징이 다르다..
출처: https://ledgku.tistory.com/54

key값은 int, flaot, tuple등 자료형을 쓸 수 있지만, set, list등 mutable한 값은 쓸 수 없다.

1) Dictionary 선언

 dict = {}
 dict = ['a' : 15, 'b':(alice,13)]

2) Dictionary 삽입 / 교체

 dict['c'] = (sumin,27)
 dict['a'] = 'hello'
 dict = ['a' : 'hello', 'b':(alice,13), 'c': (sumin,27)]

3) Dictionary 원소의 삭제

 dict = ['a' : 'hello', 'b':(alice,13), 'c': (sumin,27)]
 del dict['a']