Jaeryong

단어 변환 풀이시작 단어로부터 타겟 단어로 변환하는 문제이다. 한번에 한 글자만 변경할 수 있어, 한글자만 변경 했을 때 나올 수 있는 단어가 주어지는words 배열에 존재하는지 확인하면서 탐색을 하면 된다.코드from collections import dequedef check(current, target): cnt=0 for w1 ,w2 in zip(current, target): if w1 == w2: cnt +=1 # 단어가 하나만 다르면 변환가능! if cnt >= len(current)-1: return True return Falsedef solution(begin, target, words..

11779번: 최소비용 구하기 2 풀이다익스트라를 이용해 해결했다. 우선순위 큐를 이용해서 비용이 적은 루트를 택하면 된다. 다익스트라는 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 해당 문제에서는 최단 경로에서 거쳐가는 모든 정점을 프린트해야 하기 때문에 이부분을 따로 관리해줘야 한다. 코드import sysfrom collections import defaultdictimport heapqINF = int(1e9)n = int(input())m = int(input())graph = defaultdict(list)for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c))..

여행경로 풀이 defaultdict를 사용해서 풀었다. ICN에서 시작해서 도착 공항에서 갈 수 있는 다음 행선지가 있다면 알파벳 순으로 공항을 방문하고 없다면 정답 배열에 넣는다. 이렇게 하면 정답의 반대의 순서로 들어가게 되는데, 마지막에 정답 배열을 [::1]로 뒤집어 줘서 return하면 된다.코드from collections import defaultdictdef solution(tickets): paths = defaultdict(list) for (depart, dest) in tickets: paths[depart].append(dest) for depart in paths: paths[depart].sort(reverse=Tr..

2206번: 벽 부수고 이동하기풀이 방문처리를 3차원 배열로 만들어, 벽을 부셨는지 부시지 않았는지에 대한 여부를 저장하면 된다.벽을 만났을 때 아직 벽을 부시지 않았다면 부수고 큐에 넣어준다.코드from collections import dequen, m = map(int, input().split())grid = [list(map(int, input().strip())) for _ in range(n)]visited =[[[0]*2 for _ in range(m)] for _ in range(n)]visited[0][0][0] = 1dx=[0,0,1,-1]dy=[1,-1,0,0]def bfs(x,y,z): q = deque() q.append((x,y,z)) while q: x,y,z = ..

6064번: 카잉 달력 브루트포스(Brute-Force)완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.이 알고리즘은 예외 없이 100%의 확률로 정답만을 출력한다. 브루트포스 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.때문에 대부분 반복문과 조건문을 통해 문제를 해결하고, 높은 시간 복잡도를 가진다. 쉽게 말해 노가다 수학이다.풀이식만 세우면 해결할 수 있는 문제지만 식 세우기가 상당히 어려운 문제다... 혼자 힘으로는 도저히 식을 떠올릴 수가 없어서 다른 사람의 풀이를 참고하여 풀었다. 우선 카잉 달력에서 는 실제로 을 나타낸다는 것을 알 수 있다. 만약 M, N, x, y = 10..

리코쳇 로봇 풀이직전에 풀었던 아기돼지와 늑대 문제와 동일한 유형의 문제이다.BFS를 돌면서 장애물을 만나거나 맵 밖으로 나갈때까지 미끄러지며 탐색을 하는 유형이다. 중요한 것은 일반적인 BFS 문제와 다르게 방문했던 곳을 다시 방문할 수 있다는 것이다!코드from collections import deque def solution(board): dx = [0,0,1,-1] dy = [1,-1,0,0] n = len(board) m = len(board[0]) visited=[[0]*m for _ in range(n)] def bfs(): # 시작지점 넣어주기 q = dequ..

16441번: 아기돼지와 늑대 풀이늑대의 위치를 deque에 저장해 놓고, 각 늑대의 위치에서 BFS를 돌면서 방문처리를 하고, 모든 BFS가 끝난 후에 늑대가 갈 수 없는 초원지대를 'P'로 마킹해 주면 된다. 빙판에 있을 때는 while문을 돌면서 늑대를 계속 이동시키다가 산을 마주쳤을 때는 값을 한번 빼서 바로 전에 이동한 값을 방문한 것으로 만들고, 빙판길을 가다가 초원이 나왔을 경우 바로 초원을 방문한 것으로 만들었다.코드from collections import dequen,m = map(int, input().split())grid = [list(input().strip()) for _ in range(n)]visited = [[False]*m for _ in range(n)]dx=[0,0,..