For Programmer

이 문제는 이것만 알면 쉽게 풀 수 있다. 루트 노드를 기준으로 가장 비용이 큰 노드를 찾아간다. 그 후 그 노드에서 다시 가장 비용이 큰 노드를 찾는다. 그렇게 찾은 비용이 지름이다. import sys sys.setrecursionlimit(100000) input = sys.stdin.readline N = int(input().rstrip()) graph = [[] for _ in range(N + 1)] # 그래프의 정보를 저장할 리스트 visited = [False] * (N + 1) # 방문처리 cost = [0] * (N + 1) # 한 정점 v까지 도착할때 드는 비용을 저장할 리스트 for _ in range(N - 1): p, c, temp_cost = map(int, input().s..

간단한 트리문제이다. 0으로 이루어진 리스트를 하나 선언 후 dfs를 돌면서 하위 재귀에서 탐색한 개수를 계속 더해주면서 리턴 해주면 된다. import sys sys.setrecursionlimit(150000) input = sys.stdin.readline # dfs로 자식노드의 개수 구하기 def dfs(cur): child_count[cur] = 1 visited[cur] = True for nxt in graph[cur]: if not visited[nxt]: child_count[cur] += dfs(nxt) #하위재귀에서 탐색한 개수를 계속 더해주면서 그 값을 리턴 return child_count[cur] N, R, Q = map(int, input().split()) # 정점의 수 , ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15FZuqAL4CFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 설명이 참으로 이해하기 어렵다.. 또한 히든 케이스 예를들어) 암호코드가 처음7개가 일치하는 데도 불구하고 그 다음7개가 일치하지 않는 경우 다시 처음으로 돌아가 인덱스를 한개 증가시켜서 그다음 7개 부터 검사해야하는 방식으로 코드를 짜야하는 경우가 케이스에 있다. 이러한 예외케이스를 설명을 안해주니 찾기가 참으로 힘들었다.. 나머지는 쉽게 구현할 수 있었고 주석으로 달아놨다. import s..

간단히 dfs 나 bfs로 노드를 타고 들어가면서 그전의 노드를 부모로 설정해주는 부모를 가리키는 리스트하나만 만들면 된다. 두개 모두 코드를 올려놨다. import sys from collections import deque sys.setrecursionlimit(5000) input = sys.stdin.readline def dfs(cur): visited[cur] = True for nxt in graph[cur]: if not visited[nxt]: parent[nxt] = cur dfs(nxt) def bfs(start): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() for i in graph[v]..

이 문제... 방문처리 때문에 2시간을 소비했다. 반드시 큐에 넣기전에 방문처리를 해주고 넣자.!!!!!!!!! 문제 해결법은 간단하다. BFS가 조금 복잡하다 싶으면 3차원 방문처리를 생각하면된다. 어느 좌표 r,c가 있으면 visited[r][c][방향] 으로 처리하여 r,c 좌표에 대하여 4가지방향 동 서 남 북의 방문처리를 각각해주면 된다. 자세한 설명은 주석으로 달아 놨다. import sys from collections import deque input = sys.stdin.readline M, N = map(int, input().split()) miro = [list(map(int, input().split())) for _ in range(M)] start_r, start_c, star..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해당 문제 처음에는 일반적인 구현문제인줄 알았으나 풀다보니 dfs라는것을 알게 되었다. 전체 풀이방식은 다음과 같다. 1. 각 달마다 일 가격 * 수영장에 가야하는 해당 달의 일수 와 달가격중 싼것을 저장해준다. 2. 1에서 구해진 값들을 기준으로 한달가격으로 적용하거나 일부 달을 3달가격으로 적용하는 것 중 어떤 값이 모든 경우를 계산하여 어느 값이 더 적은지 구해준다.(dfs를 이용) 3. 2에..

위 문제는 정답률이 22%에 해당하는 괴랄한 문제이다. 골드4치고는 어려운데 그 이유는 벽을 부술때 방문처리와 부수지 않을때 방문처리를 따로 해주어 검사해야하기 때문이다.(3차원 리스트로 처리해주어야함) 또한 벽을 1번 부쉈으면 2번이상 못부수게 처리도 해주어야 하기 때문에 쉽지않았다. (다풀어놓고 자꾸 틀리길래 무엇이 잘못됐나 한참봤는데 큐에서 꺼낸 값을 직접 바꾸면 그 꺼낸 방향에서 이동하는 상하좌우의 모든 방향에 영향을 준다.... 이걸 못찾아서 40분 정도 걸렸다... 꼭 실수하지 마시길.. 주석으로 해당 부분 설명해놨다.) from collections import deque N, M = map(int, input().split()) miro = [list(map(int, input())) fo..

해당 문제 처음에 문제이해하기가 힘들어서 조금 해맸다. 문제에서 결국 구하라는 것은 육지에서 가장 멀리갈 수 있는 길의 거리를 찾으라는 문제이다. 그냥 육지 지점을 모두 좌표로 저장해서 모든 육지지점에서 부터 출발해서 거리를 계산해서 가장큰 값을 찾는방식으로 했는데 파이썬으로 풀면 시간초과가 난다. 그래서 찾아보니 가운데에 껴있는 육지들 즉, 위아래로 그리고 양옆으로 모두 육지인 애들은 어차피 최대의 거리가 나올수 없기 때문에 그냥 검사하지 않고 넘어가는 식으로 코드를 구성했다. 굳이 따로 구현은 하지 않았지만 관심있으면 찾아보기 바란다. import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().s..