11725번: 트리의 부모 찾기 (acmicpc.net)

#루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정할 때 각 노드의 부모를 구하는 프로그램
from collections import deque
import sys

n = int(sys.stdin.readline()) #노드의 수

graph = [set() for i in range(n+1)]

#인접리스트 구현
for _ in range(n-1): # 정점이 n개이므로 간선은 n-1개 있음
    a, b = map(int, sys.stdin.readline().split())
    graph[a].add(b)
    graph[b].add(a)

visited = [0 for i in range(n+1)]

queue = deque([1])
while queue:
    x = queue.popleft()
    for node in graph[x]:
        if visited[node] == 0:
            visited[node] = x # 방문했을 때 0을 대체하게 되는 것은 부모 번호이다.
            queue.append(node)

for i in range(2, len(visited)):
    print(visited[i])

여러번 런타임 에러가 난 이유: 마지막 출력하는 for문에서 range를 1부터로 설정해놓아서이다. 

1은 루트노드인데, 루트노드의 부모 노드는 출력할 필요가 없다.. 

그리고 인접리스트 구현할 때도 처음에 for _ in range(n)이렇게 했었는데, n은 정점의 개수이므로 간선은 n-1개가 된다.

코딩테스트 연습 - 순위 | Programmers School

나의 풀이

def solution(n, results):
    graph = [[0]*(n+1)for _ in range(n+1)]
    for res in results:
        win, lose = res[0], res[1]
        graph[win][lose] = 1
        graph[lose][win] = -1

    for i in range(n+1):
        for j in range(n+1):
            for k in range(n+1):
                if graph[i][j] == -1 and graph[j][k] == -1:
                    graph[i][k] = -1
                    graph[k][i] = 1
                elif graph[i][j] == 1 and graph[j][k] == 1:
                    graph[i][k] = 1
                    graph[k][i] = -1
                        
    answer = 0  
    
    for player in graph:
        if player.count(0)==2:
            answer+=1
        
    return answer

a가 b를 이기고 b가 c를 이겼다면,
a는 c를 이긴 것이고

c는 a에게 진 것이다.

--> for문을 세 개 도는 플로이드 워셜 알고리즘 이용

처음에 "c는 a에게 진 것이다!" 라는 부분을 코드에 표현하지 않아서
몇 개의 테스트케이스에서 부적확한 결과가 나왔다.

간접적인 승패의 결과를 전파할 때. 나의 풀이에서는 이김 = 1, 짐 = -1로 표현하고 

최종적으로 승패를 알 수 없는 0의 개수를 세서 답을 구했기 때문이다.


만약 진 것은 표현하지 않기로 했다면?

마지막에 1의 숫자를 셀 때 해당 인덱스를 행으로 하는 곳에서도 세고, 해당 인덱스를 열로 하는 곳에서도 세면 된다.
(열로 봤을 때 1로 표현된 것은 그 행의 인덱스를 가진 선수에게 졌기 때문임)

코딩테스트 연습 - 가장 먼 노드 | Programmers School

# 풀이 1

def solution(n, edge):
    graph = [[]for _ in range(n+1)]
    not_visited = [i for i in range(2, n+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    

    far = {1}
    while not_visited:
        farther = set()
        for node in far:
            for j in graph[node]:
                if j in not_visited:
                    not_visited.remove(j)
                    farther.add(j)
        if not farther:
            return 1
        far = farther
    return len(far)

테스트 케이스 10개 중 1 개에서만 시간초과가 나옴.

# 바로 deque 도입한 풀이 2

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    dist = [0]*(n+1)
    for i, j in edge:
        graph[i].append(j)
        graph[j].append(i)
    
    queue = deque([1])
    while queue:
        x = queue.popleft()
        if graph[x]:
            for k in graph[x]:
                if k == 1:
                    continue
                if dist[k] == 0:
                    dist[k] = dist[x]+1
                    queue.append(k)
    
    a = max(dist)
    answer = dist.count(a)
    
    return answer

시간 초과 없이 모든 테스트케이스를 통과했다.

Find Center of Star Graph - LeetCode

풀이 1

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        a, b = edges[0][0], edges[0][1]
        if a in edges[1]:
            return a
        else: 
            return b

풀이 2

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if edges[0][0]== edges[1][0]:
            return edges[0][0]
        elif edges[0][0]== edges[1][1]:
            return edges[0][0]
        else:
            return edges[0][1]

두 번째가 조금 더 빨랐다..!

2606번: 바이러스 (acmicpc.net)

내 풀이:

computers = int(input())  # 전체 컴퓨터의 수
n = int(input())   #직접 연결되어 있는 컴퓨터 쌍의 수


#인접리스트로 만들기!
 
list=[[] for _ in range(computers+1)]
 #이차원 리스트 초기화

for i in range(n):
    a, b = map(int, input().split())
    list[a].append(b)
    list[b].append(a)
    #각각의 노드에 연결된 노드들의 정보를 기록


#dfs 함수
connected=[] #1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터들을 추가할 곳

def dfs(x):
    global connected
    for i in list[x]:
        if i!=1 and i not in connected:
            connected.append(i)
            dfs(i)
    return len(connected)


print(dfs(1))

2178번: 미로 탐색 (acmicpc.net)

내 풀이