0과 1의 쉼터

문제https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이항공권의 정보가 주어졌을 때, 모든 공항을 전부 방문할 수 있는 경우를 찾고 들른 공항의 순서를 출력하는 문제다.정답이 여러개 존재하는 경우 공항의 순서를 사전순으로 출력해야 한다.일단, 입력받은 항공권의 정보에 대해 다음과 같이 그래프를 생성하고, 역순으로 정렬해줬다.from collections import defaultdictdef solution(tickets): graph = defaultdict(list) for ..

문제https://www.acmicpc.net/problem/1405 풀이로봇이 확률에 따라 상하좌우로 움직인다고 한다.이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.if __name__ == '__main__': visited = [[False] * 29 for _ in range(29)] # Input N, *D = map(int, input().split()) D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1)..

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y..

문제오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  visited[R] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ ..