개발미정

people = int(input()) a, b = map(int, input().split()) M = int(input()) relation = [[] for _ in range(people+1)] for m in range(M): st, en = map(int, input().split()) relation[st].append(en) relation[en].append(st) result = [] def checkRelation(x): if len(relation[x]) == 0: return result.append(x) # 만약 x가 b라면 끝 if x == b: return True for i in relation[x]: if i in result: continue if checkRelatio..

두 개의 동전이 있고, 보드가 있을 때 두 개의 동전 중 하나만 떨어지면서 그 때의 최소 count를 구하는 문제이다. 문제 접근 BFS로 접근하였고, 다음 3가지만 고려하였다. 1. 두 개의 동전이 모두 안 떨어진 경우 2. 두 개의 동전이 모두 떨어진 경우 3. 한 개의 동전만 떨어진 경우 남 -> 동 -> 북 -> 서 순으로 이동하였고, 1번 경우에는 다음 가고자 하는 위치가 벽인 경우만 고려해주었다. 2번 경우에는 count를 할 필요가 없기 때문에 pass 하였다. 3번인 경우 현재 최소 count와 현재까지의 count를 비교하여서 최소값을 구하였다. 정답 코드 from collections import deque rows, cols = map(int, input().split()) BRD =..

프로그래머스에 DFS/BFS -> 3번째 문제인 "단어 변환" 이다. 주어진 단어들만을 돌면서 begin -> target으로 가는 경로 중 최단 경로의 길이를 구하는 문제이다. 주어진 단어들로만 변경이 가능하고, 한 글자만 다를 경우에만 change가 가능하다. def solution(begin, target, words): answer = 0 min_cnt = 0xffff if target not in words: return 0 def dfs(cur, cnt): nonlocal min_cnt # 최소 cnt보다 현재 cnt가 더 큰 경우, 더 볼 필요가 없어지므로 return if min_cnt < cnt: return # cnt가 words의 길이보다 클 경우 이미 모든 경로를 탐색하게 된 것이므..

프로그래머스의 코딩테스트 연습 -> DFS/BFS 문제 중 마지막 문제인 "여행경로" 이다. "ICN"으로 무조건 시작해서 모든 도시를 지나는 경로들 중 알파벳 순서로 되어있는 경로를 구하면 된다. 먼저, 모든 도시를 지나는 경로들 중 알파벳 순서로 먼저인 경로를 구하기 위해서 tickets 배열을 sort 해주었다. 그래야 for문을 돌 때 순서대로 돌 수 있기 때문이다. def solution(tickets): answer = [] s = ["ICN"] visited = [0] * len(tickets) def dfs(cur, visited, tickets, state): nonlocal answer if len(state) == len(tickets) + 1: answer = state return..

문자열 s와 t가 주어지고 s를 변형하여서 t를 만들 수 있는지 확인하는 문제이다. 처음에 s에서 t로 백트래킹으로 접근했는데 계속된 시간초과.. 로 구글링해서 겨우 풀었다... ㅠㅠ 쉬워보였는데 은근 안풀렸던 문제! 첫 번째 풀이 정방향 => 시간초과 def change(s): global result if len(s) ..

bfs를 이용한 기본적인 문제! bfs를 완벽히 이해했다면 쉽게 풀릴문제이다. 8가지의 방향으로 이동하도록 구현하였다. T = int(input()) from collections import deque # q = [] # 방향 dx = [-2, -1, 1, 2, 2, 1, -1, -2] dy = [-1, -2, -2, -1, 1, 2, 2, 1] def bfs(): visited = [[0 for _ in range(N)] for _ in range(N)] visited[stX][stY] = 1 q = deque([(stX,stY)]) while q: newX, newY = q.popleft() if newX == enX and newY == enY: return visited[newX][newY] f..