수학과의 개발자 도전기

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

노드말고 간선 가중치까지 주어져서 어떻게 그래프를 구현해야할지 고민이 많았던 문제다 

 트리의 지름은 결국 잎노드에서 잎노드로 이루어진다고 생각했어서 잎노드를 구하고 잎노드-잎노드 사이의 가중치를 모두 구한 후 거기서 최댓값을 구하는 거라고 생각했는데, 메모리 초과가 발생했다.

(경험상 모든 것을 다 탐색하는 거는 시간초과, 메모리초과가 발생한다. 효율적으로 코드 작성하는 거 연습하기. 7/30)

그 외에는 모르겠어서 구글링을 해보았더니 

그래프 구현은 노드에 연결된 노드와 간선 가중치를 모두 삽입하는 것으로 진행하는 것 같다 

1. 루트노드에서 가장 먼 노드를 dfs로 구한다음(1노드에서 가장 먼거)

2. 1번에서 구한 가장 먼 노드에서 한번 더 가장 먼 노드를 dfs로 구현한다 

3. 2번에서 구한 길이 중 가장 먼 길이가 정답이 된다 

-정답풀이: 

import sys
sys.setrecursionlimit(10**5)

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

def dfs(x,weight):
    for i in graph[x]:
        a,b=i
        if distance[a]==-1:
            distance[a]=weight+b
            dfs(a,weight+b)
            
for _ in range(n-1):
    a,b,c=map(int,input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])
    
#1번 노드에서 가장 먼곳을 찾는다(잎노드 찾기?)    
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))

-풀이 이해: 

x와 이어진 i번째 노드에 대하여 

i번째 노드와 연결된 노드와 가중치를  a,b에 입력한 후 

연결된 노드를 방문하지 않았다면 distance[a]에 주어진 무게와 가중치를 넣고 이동시킨다 

dfs 다시 실행

def dfs(x,weight):
    for i in graph[x]:
        a,b=i
        if distance[a]==-1:
            distance[a]=weight+b
            dfs(a,weight+b)

각 노드에 연결된 노드와 가중치를 넣어서 그래프를 구현한다 

for _ in range(n-1):
    a,b,c=map(int,input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])

1의 weight는 0 이므로 방문하지 않은 노드의 값을 0으로 하면 안되기에 -1로 distance를 초기화 해준다 

dfs(1,0)을 통해 1에서 가장 먼 노드를 구한다 

#1번 노드에서 가장 먼곳을 찾는다(잎노드 찾기?)    
distance=[-1]*(n+1)
distance[1]=0
dfs(1,0)

루트 노드로부터 가장 멀리에 있는 노드를 구한다(distance가 최대인 인덱스의 값을 구하는 것)

distance 다시 한번 더 초기화 하고, 

가장 먼 노드를 루트노드로 두고 dfs를 진행한다 

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

print(max(distance))

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

bfs를 구현하는 것보다 빙산이 분리된 것을 확인하는 코드를 알아내기가 어려웠던 것 같다.

빙산 깎는건 주변의 0이 있으면 하나씩 깎는데 먼저 깎아버리면 주변 빙산에 영향을 주므로 

해당 빙산 주위에 잇는 바다의 갯수를 구한 뒤 한번에 깎아야 한다.

빙산이 분리 된 것을 확인하는 게 쉽지 않았는데, bfs가 1번 실행되면 아직 빙산 뭉치가 있는 것이지만, bfs가 2번 실행된다면 

그때는 분리가 된 것이므로 그걸 true,false 값으로 해야할 것 같았다.

근데 구현을 어떻게 하는지 몰랐다. 

풀이를 보면서 또 배워야할 것 같다 

-정답풀이: 

그래프를 돌면서 빙하 주변에 있는 바다의 갯수를 구한다 ->ok

빙하도 깎아야하고, year도 구해야하니까 for for로는 다 해결되지 않는다. 이럴땐 while True문 이용하기

s가 0이 아니면 빙하를 뜻하므로 빙하에 대해서 bfs를 실행해서 count 리스트를 만들고, result에 bfs 실행 횟수를 삽입한다(1번)

다음에 빙하를 깎는다 

빙하가 음수값을 가지면 0으로 바꿔준다

len(result)가 0이라면 bfs가 끝나지 않는 것이므로 break를 반환해주고

len(result)>=2라면 분리가 된 것이므로 check=True를 해주고 나올 때 Year+=1을 해준다

check 값 (True,False)에 따라 값을 출력하면 끝

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

문제의 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프가 이분그래프라고 이해하면 될 것 같다. 

방문하지 않은 노드에 한하여 이전 노드와 다른 색깔(-1 또는 1)을 부여한다

만약 이전노드와 현재 노드가 같은 색인데 현재노드와 이전노드 모두 방문한적이 있다면 False를 반환한다 

문제를 input받은 다음에 bfs(i)값이 False라면 'NO'를 출력하고,

아니라면 'YES'를 출력한다

queue에 append하는 것도 잊지말자!!

처음에 visit=1값 하는 것도 잊지 말기 

-정답풀이 :

from collections import deque

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                visit[i]=-visit[x]
                queue.append(i)
            elif visit[i]==visit[x]:
                return False
    return True  

t=int(input())
for _ in range(t):
    v,e=map(int,input().split())
    graph=[[] for _ in range(v+1)]
    visit=[0]*(v+1)
    flag=True
    for _ in range(e):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1,v+1):
        if not visit[i]:
            if not bfs(i):
                flag=False
                break
    if flag:
        print('YES')
    else: 
        print('NO')

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

쉬운 문제인데 못 풀었다

너무 복잡하게 생각해서 그런것 같은데 기본 bfs를 이용하면 쉽게 풀린다 

-정답풀이: 

10번,18번,21번을 생각하지 못해서 틀린 문제다

from collections import deque

n,m= map(int,input().split())
graph=[[] for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(v):
    num=[0]*(n+1)
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                num[i]=num[x]+1
                queue.append(i)
                visit[i]=1
    return sum(num)
            

ans=[]
for i in range(1,n+1):
    visit=[0]*(n+1)
    ans.append(bfs(i)) #케빈 값들 넣는다
    
k=min(ans)
print((ans.index(k))+1)