수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/1068

Gold level 5문제다 

문제를 이해한 것으로는 1. 노드를 없애고 2. 자식 노드를 구별해서 그것의 갯수를 구해야한다고 생각했다. 

1번을 구체적으로 하자면

처음 지운 노드의 모든 자식노드들도 삭제되어야 하므로 그들의 인덱스 값에 -2를 대입해야하는데, 이때 dfs를 사용해야한다고 생각했다.

-2를 넣은 이유는 -1은 루트 노드를 가리키기 때문에 다른 숫자로 삭제 노드를 표현해야 했다 

배열 전체를 탐색하며, 방금 삭제한 인덱스를 부모로 가지는 노드를 찾아 dfs함수를 재귀호출한다 

2번을 구체적으로 하자면 

dfs로 노드들을 삭제한 뒤 삭제되지 않고 남은 트리에서 자식노드를 구해서 그것의 갯수를 구하면 된다 

이 문제에서 나는 1번을 구현하는 것이 어려웠던 것 같다. 2번은 비교적 쉬웠다 

-정답풀이: 

n=int(input())
s=list(map(int,input().split()))
k=int(input())

#k노드 지우고 트리 정리
def dfs(v,s):
    s[v]=-2
    for i in range(n):
        if v==s[i]: #v가 부모노드일때
            dfs(i,s) #v의 자식노드들도 삭제하기 
        

dfs(k,s)     
cnt=0        
for i in range(n):
    if s[i]!=-2 and (i not in s):
        cnt+=1
print(cnt)

-틀린 풀이 피드백:

dfs에서 초기값을 넣으면 그 값부터 -2로 바뀐 후 진행되므로 15-19라인은 굳이 필요 없었다. 이 내용을 dfs 구현 내용에 넣으면 된다(물론 둘다 코드는 틀렸다)

그리고 22-25라인은 필요 없다. 왜냐하면 이미 주어진 리스트 s의 값들이 부모노드를 의미하므로 굳이 parent라는 리스트를 따로 만들어서 값을 넣을 필요는 없다 -2가 아니면 다 부모 노드이므로.

-문제:https://www.acmicpc.net/problem/9466

Gold level3 문제이다 

문제에서 팀을 이루는 경우는 두가지 인데, 

1) 자기 자신과 팀을 이루는 경우

2) 두명이상이고, 사이클을 이루는 경우

위 두 상황은 별개라고 생각해서 1)번을 특히 어떻게 구현해야 할지 잘 몰랐는데 1)번 경우도 사이클을 이루는 경우 이므로 

결과적으로 cycle을 이루는 것에 대해서만 함수를 작성하면 된다는 것을 구글링을 통해 알았다 

사이클이 되는 조건: 첫번째수 == 마지막 수가 가리키는 숫자

예) 4-7, 7-6, 6-4는 사이클을 이룬다. 6이 가리키는 숫자가 처음 시작인 4이기 때문

-정답풀이: 

import sys
sys.setrecursionlimit(111111)

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)
        
for _ in range(int(input())):
    n=int(input())
    s=[0]+list(map(int,input().split()))
    visit=[1]+[0]*n
    result=[]
    for i in range(1,n+1):
        if not visit[i]:
            cycle=[]
            dfs(i)
    print(n-len(result))

-풀이 이해:

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)

10번에 if number in cycle: 이 의미하는 것은 마지막 숫자가 가리키는 숫자가 cycle이라는 리스트 안에 있다면 그건 cycle을 이룬다는 것이다

그래서 number가 사이클의 시작이므로 number의 인덱스 부터 끝까지의 리스트를 result에 추가한다

사이클을 이루지 않는 경우는 다음 dfs를 실행하면 된다 

-문제: https://www.acmicpc.net/problem/2210

쉬운 문제였는데 잘 안풀렸던 문제. 재귀를 돌려야해서 동작 예측을 하는게 어려웠던 것 같다. 

문제 풀 때 고민했던 건 1. 지나갈 때 만나는 숫자는 어디에 입력하는 것이고 2. 딱 5번만 이동은 어떻게 하는지 

-정답풀이: 

2번의 해답은 문자 길이가 6이고, result안에 없는 문자라면 result에 삽입하고 return을 한다 

def dfs(x,y,num):
    if len(num)==6:
        if not num in result:
            result.append(num)
        return

1번의 해답은 위치를 알려주는 x,y 말고 num이라는 파라미터를 더 추가해서 이 숫자에 저장하면서 진행하면된다. 

한칸씩 진행할 때마다 num에는 숫자가 쌓일 것이고, 이 길이가 6이 된다면 result에 넣고 끝난다 

def dfs(x,y,num):
    if len(num)==6:
        if not num in result:
            result.append(num)
        return  

    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            ans= num+s[nx][ny]
            dfs(nx,ny,ans)
            
s=[list(input().split()) for _ in range(5)]
result=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(5):
    for j in range(5):
        dfs(i,j,s[i][j])
        
print(len(result))

-문제: https://www.acmicpc.net/problem/1167

주어진 리스트에 따라 그래프 입력하는 방식이 달라져서 그래프 구현 코드를 다르게 구현했지만 계속해서 IndexError가 발생했다

이유는 찾아봐야할 것 같다 

참고한 블로그 

-정답풀이:

from collections import deque
import sys 
input=sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n + 1)]

for _ in range(n):
    result = list(map(int, input().split()))
    for i in range(1, len(result) - 2, 2):
        graph[result[0]].append((result[i], result[i + 1]))


def bfs(start):
    visit = [-1] * (n + 1)
    queue = deque()
    queue.append(start)
    visit[start] = 0
    _max = [0, 0]

    while queue:
        t = queue.popleft()
        for x,y in graph[t]:
            if visit[x] == -1:
                visit[x] = visit[t] + y
                queue.append(x)
                if _max[0] < visit[x]:
                    _max = visit[x], x

    return _max


distance, leaf = bfs(1)
distance, leaf = bfs(leaf)
print(distance)

-틀린풀이:

틀린 이유 (7/30)

while로 일단 돌리면 시간초과 나고, 

첫번째, 마지막 인덱스 빼고 두개씩 인덱스가 진행되어야 하는데 한개씩 진행된다 

입력값 처리를 제대로 못해서 틀린 것 같다