수학과의 개발자 도전기

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

일단 하나의 팀이 만들어지려면 하나의 싸이클이 만들어져야하는데, 이는 탐색을 돌다가 마지막 사람이 선택한 사람이 첫번째 사람일 때 팀이 완성된다고 이해했다. 결과적으로 정답과 로직은 맞지만 틀린 부분이 많다. 

탐색을 돌다가 다음 사람이 리스트에 있을 때, 다음 사람까지 리스트에 추가한다. 

만약 마지막 사람과 첫번째 사람이 같다면 싸이클이 만들어진 것이므로 전체 길이-1을 한 값을 n에서 빼준다 

그런데 여기에 문제가 있다 

visit처리를 하지 않아서 같은 팀이 중복으로 생길 수 있다 -> 틀린 답을 출력

그래서 나름 고쳐본다고 했는데, 잘 안돼서 전에 풀었던 풀이를 봤다. 

그러니까 result는 팀을 만든 모든 사람들이 있고, 각각의 팀은 cycle 리스트에 삽입한 후 진행한다 

- 정답 풀이 :

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

#[4,7,6]이 중복되게 세면 안되니까 visit 사용
#싸이클이 되는 경우는 방문한 숫자 중에 cycle에 있는 경우

def dfs(x):
    global result
    visit[x]=1
    cycle.append(x)
    if visit[data[x]]:        
        if data[x] in cycle:
            result+=cycle[cycle.index(data[x]):]
    else: 
        dfs(data[x])                

for _ in range(int(input())):
    n=int(input())
    data=list(map(int,input().split()))
    data=[0]+data
    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(x):
    global result
    result.append(x)
    if data[x] in result:
        result.append(data[x])
    else:         
        dfs(data[x])                

for _ in range(int(input())):
    n=int(input())
    data=list(map(int,input().split()))
    data=[0]+data
    count=n
    for i in range(1,n+1):
        result=[]
        dfs(i)
        if result[0]==result[-1]:
            count-=(len(result)-1)
        else:
            continue
    print(count)

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

Silver Level2 문제

행렬의 크기가 5x5라서 완전탐색을 하면서 각 위치에서 5번 이동해서 만든 6자리 수를 비교하려고 했다

처음에는 global temp를 선언한뒤 움직일때마다 숫자를 temp에 붙이는 식으로 생각했는데, 

dfs로 진행하다보니 그렇게 하면 하나의 케이스를 온전히 못 담기도 하고, 메모리 초과가 난다 

그래서 하나의 깊이마다 temp를 담기 위해 temp 파라미터를 추가한 후 그 길이가 6일 때 dfs를 멈춘다 

중복된 숫자를 넣지 않는 방법은 다음 코드를 작성하면 된다 

if not temp in answer:

다음에서 return을 두번째 if 안에서 안 하고, 첫번째 안에서 하는지 궁금했다. 

생각해보니까, 일단 길이가 6이 되면 그 탐색은 끝나는건데, 중복된 것이 있으면 answer에 넣지 않은 상태에서 끝나는거고, 중복된 것이 없으면 answer에 삽입하고 끝나는 거니까 그 두가지 경우를 모두 생각해서 return의 위치가 정해진 것 같다. 

만약 두번 째 if 안에 return이 있으면 중복된 경우 멈추지 않으니까 (내 생각이고, 틀릴 수도 있다)

이 생각을 기반으로 정답 풀이 코드를 조금 고쳤다. 이렇게 작성해도 정답이 뜬다 

if len(temp)==6:
        if not temp in answer:
            answer.append(temp)
        return

- 정답 풀이 :

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

data=[]
for _ in range(5):
    data.append(list(input().split()))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=[]

def dfs(x,y,temp):
    if len(temp)==6:
        if temp not in answer:
            answer.append(temp)
            return
        else: #중복되는 결과는 그냥 반환하기 
            return   
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            num=temp+data[nx][ny]
            dfs(nx,ny,num)

for i in range(5):
    for j in range(5):
        dfs(i,j,data[i][j])
        
print(len(answer))

- 시도해본 풀이 :

메모리 초과로 실패했다 

import sys
sys.setrecursionlimit(10**6)

data=[]
for _ in range(5):
    data.append(list(input().split()))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=[]
temp=''

def dfs(x,y):
    global temp
    if len(temp)==6:
        return temp    
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<= nx < 5 and 0 <= ny < 5 :
            temp += data[nx][ny]
            dfs(nx,ny)
            
for i in range(5):
    for j in range(5):
        result=dfs(i,j)
        if result not in answer:
            answer.append(result)
            
print(len(answer))

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

바로 전에 풀었던 트리의 지름과 같은 문제이지만 다른 점은 정점과 간선의 정보를 주는 방식이다. 

하나의 정점에 연결된 간선과 가중치 묶음이 여러개로 하나의 리스트로 주어진다 

그래서 인덱스 0과 -1를 빼고 두개 단위로 정점에 추가해주면 된다(처음에는 이 부분을 while로 돌렸는데 시간초과가 났다. 그래서 for문으로 돌렸더니 통과했다)

나머지 부분은 전 풀이와 동일하게 dfs와 distance 리스트를 이용해서 구했다 

dfs로 돌린거라 bfs보다 3배 정도 시간이 더 걸렸다 

- 정답 풀이 : 

import sys
input=sys.stdin.readline

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

for _ in range(n):
    result=list(map(int,input().split()))
    x=result.pop(0)
    result.pop(-1)
    for i in range(0,len(result),2):
        data[x].append([result[i],result[i+1]])
        data[result[i]].append([x,result[i+1]])
        
def dfs(x,weight):
    for i in data[x]:
        a,b=i
        if distance[a]==-1:
            distance[a]=b+weight
            dfs(a,b+weight)
            
distance=[-1]*(n+1)
distance[1]=0
dfs(1,0)

start=distance.index(max(distance))
distance=[-1]*(n+1)
distance[start]=0
dfs(start,0)

print(max(distance))

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

잎노드에서 시작을 해야할 것 같은데, 잎 노드에서 가장 먼 잎 노드를 어떻게 찾지?하며 어떻게 풀어야할지 몰랐던 문제다 

풀이 방법은 

일단 루트 노드에서 가장 먼 잎 노드를 구한다. 

그 잎노드에서 가장 멀리 있는 잎노드를 구한다

거기까지의 가중치 합을 출력하면 된다 

- 정답 풀이 : 

import sys
sys.setrecursionlimit(10**6)

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

for _ in range(n-1):
    a,b,c=map(int,input().split())
    data[a].append([b,c])
    data[b].append([a,c])
    
def dfs(x,weight):
    for i in data[x]:
        a,b=i
        if distance[a]==-1:
            #a노드 방문처리 
            distance[a]=b+weight
            dfs(a,b+weight)
distance=[-1]*(n+1)
distance[1]=0
dfs(1,0)

#루트노드로부터 가장 멀리 있는 잎 노드 번호 구하기 
start=distance.index(max(distance))
distance=[-1]*(n+1)
#해당 잎 노드를 루트노드로 가장 먼 잎 노드를 찾는다 
distance[start]=0
dfs(start,0)
            
print(max(distance))