[Python/파이썬] 백준 16437번: 양 구출 작전

문제 풀이 경로는 유일하므로 방문 처리는 따로 구현하지 않았다. 트리의 리프 노드까지 재귀를 통해 이동하고, 리턴 값을 통해 문제를 풀었다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n + 1)] for i in range(2, n + 1): type, amount, root = input().split() amount, root = int(amount), int(root) if type == 'W': amount = -amount tree[root].append((i, amount)) def dfs(x, amount): for next, nex..

[Python/파이썬] 백준 17616번: 등수 찾기

문제 풀이 등수를 찾을 노드 위로 몇 개의 노드가 있는지, 아래로 몇 개의 노드가 있는지 구하면 된다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n, m, x = map(int, input().split()) up = [[] for _ in range(n + 1)] down = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) down[a].append(b) # a 아래에 b up[b].append(a) # b 위에 a visited = [False] * (n + 1) def dfs(x, graph, cnt): visited[x] ..

[Python/파이썬] 백준 16947번: 서울 지하철 2호선

문제 풀이 먼저 사이클을 구한다. 사이클은 하나만 존재하고, 길이는 3 이상 이어야 한다. for i in range(1, n + 1): if not visited[i]: tmp = [] if dfs(i, tmp): print(cycle) break def dfs(x, tmp): global cycle visited[x] = True tmp.append(x) for next in graph[x]: if visited[next]: if next in tmp: if len(tmp[tmp.index(next):]) >= 3: cycle = set(tmp[tmp.index(next):]) return True continue dfs(next, tmp) tmp.pop() 사이클을 이루는 노드에서 시작하여 깊이를 ..

[Python/파이썬] 백준 3584번: 가장 가까운 공통 조상

문제 풀이 백준 LCA 문제와 동일한 줄 알았는데 아니었다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 차이점은 LCA의 경우 양방향 간선으로 입력이 주어지지만, 가장 가까운 공통 조상의 경우 단방향으로 간선이 주어진다. 또한 LCA는 루트 노드가 1로 고정되지만, 가장 가까운 공통 조상의 경우 루트 노드를 직접 구해야 한다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin..

[Python/파이썬] 백준 2573번: 빙산

문제 풀이 DFS문제, 다만 조금 까다롭게 구현해야 한다. "만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다." 해당 조건을 구현하지 않아 62%에서 틀렸습니다가 나왔다. [반례] 5 5 0 0 0 0 0 0 2 2 2 0 0 2 2 2 0 0 2 2 2 0 0 0 0 0 0 답 : 0 틀린 답 : 3 또한 DFS로 풀 경우 sys.setrecursionlimit(10**4) setreucrsionlimit에 너무 큰 값을 넣으면 메모리 초과가 나온다. 주의할 것!! 코드 import sys sys.setrecursionlimit(10**4) input = sys.stdin.readline n, m = map(int, input().split()) graph = [..

[Python/파이썬] 백준 2668번: 숫자고르기

문제 풀이 사이클을 찾는 문제이다. 아래 풀이와 거의 동일하다. https://ku-hug.tistory.com/169 [Python] 백준 9466번: 텀 프로젝트 문제 풀이 사이클을 판별하는 문제이다. 1. 문제에서 주어진 배열을 parent 배열이라 하자. 2. 사이클을 판별하기 위해 이때까지 방문한 노드를 cycle 배열에 저장, 방문 처리를 위해 visited 배열을 생 ku-hug.tistory.com 코드 import sys input = sys.stdin.readline n = int(input()) graph = [0] visited = [False] * (n + 1) cycle = [] ans = [] for _ in range(n): graph.append(int(input())) d..

[Python/파이썬] 백준 9466번: 텀 프로젝트

문제 풀이 사이클을 판별하는 문제이다. 1. 문제에서 주어진 배열을 parent 배열이라 하자. 2. 사이클을 판별하기 위해 이때까지 방문한 노드를 cycle 배열에 저장, 방문 처리를 위해 visited 배열을 생성 3. 1번 노드를 방문했을 때 4. 1번 노드와 연결된 3번 노드 방문 각 노드를 방문하고, 그 노드와 이어진 노드를 계속 방문한다. 만약 이미 방문한 노드이고 사이클 배열에 해당 노드가 존재하면 사이클이 형성되었다는 것이다. 위 과정을 직접 해보면 이해가 쉽다. 코드 import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline def dfs(st): global team visited[st] = True cycle.append(s..

[Python/파이썬] 백준 16929번: Tow Dots

문제 풀이 시작 지점과 같은 문자인 경우 dfs를 수행하고 길이가 4 이상이고 시작 지점으로 돌아온 경우 "Yes"를 출력하면 된다. 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [list(input().rstrip()) for _ in range(n)] tempVisited = [[False] * m for _ in range(n)] dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) def dfs(c, sti, stj, nowi, nowj, cnt): for dx, dy in dir: ni, nj = nowi + dy, nowj + dx if (sti, stj) == (ni, n..

[Python/파이썬] 백준 1987번: 알파벳

문제 풀이 dfs + 백트래킹으로 풀었다. pypy로 제출 중복된 문자를 체크하기 위해 alpha 배열 생성 (alpha[0] = True인 경우 A칸을 지났다는 의미) alpha = [False] * 26 ord('A') - 65 이런 식으로 인덱스를 맞춰주었다. 그 후 백트래킹을 했다. 코드 import sys input = sys.stdin.readline r, c = map(int, input().split()) graph = [list(input().rstrip()) for _ in range(r)] alpha = [False] * 26 dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) ans = 0 def condition(ni, nj): return ni < 0 or ..

[Python/파이썬] 백준 1068번: 트리

문제 풀이 입력받은 정보를 바탕으로 각 노드의 자식 노드를 저장하는 child 배열을 만들었다. 삭제할 노드의 경우 child 배열에 추가하지 않았다. n = int(input()) parent = list(map(int, input().split())) delNode = int(input()) child = [[] for _ in range(n)] for idx in range(n): if parent[idx] == -1 or idx == delNode: continue child[parent[idx]].append(idx) 자식 노드가 없다는 것은 리프 노드임을 의미 제거할 노드의 자식 노드들을 전부 리프 노드를 만들기 위해 해당 노드에 -1 대입 def dfs(d): # 리프 노드인 경우 if ch..