본문 바로가기
728x90

DFS37

[python] 백준 1103 게임 문제 해결 DFS를 써야한다는 것은 쉽게 파악할 수 있다. 다만 떨어질 때 까지 옮겨지는 횟수를 세는 것으로 숫자가 커질 수 있으므로 dp를 사용하여한다. 숫자가 커지면 거의 DP를 사용해야 하는 것 같다. 한번 방문한 곳을 또 방문할 수 있으면 사이클을 돌 수 있고 무한반복이 가능하므로 -1을 출력하면 된다. 그렇지 않으면 떨어질 때 까지 혹은 방문한 지점이 나타날 때 까지 계속해서 DFS를 이용해서 나아가면 된다. CODE import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(sx, sy, cnt): global answer answer = max(answer, cnt) dxs = [1,-1,0,0] dys = [0,0,.. 2024. 1. 30.
[python] 백준 2533 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 해결 트리를 이용해야하는데 어떻게 이용해야할지 고민을 많이 했다. 부모-자식 중에서 적어도 한 명은 얼리 어답터여야한다. 따라서 dp를 이용해서 부모가 얼리 어답터일 때(dp[parent][1])일 때와 부모가 얼리 어답터가 아닐 때 (dp[parent][0])를 구분을 해서 알고리즘을 풀어나가면 되겠다라는 생각을 한다. dp[i][j]는 i번째 노드가 j상태일때 i번째 밑에 있는 노드.. 2023. 9. 27.
[python] 백준 14267 회사 문화 1 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 해결 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다. 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다. 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 .. 2023. 9. 26.
[python] 백준 22856 트리 순회 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 해결 트리의 간선 지나간 횟수를 셀 수 있는가 문제 전체 이동하고 왕복했을 때 지나간 간선 개수 - 오른쪽으로만 이동했을 때 끝까지 간 편도 간선 개수 DFS를 이용해 간선의 개수를 세는 것이 편하다. 자식 노드는 최대 두 개이다. (1개 일 때는 오른쪽 노드를 -1로 정의) CODE import sys input = sys.stdin.readline sys.setrecursionlimit.. 2023. 9. 24.
728x90