수학과의 개발자 도전기

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

주어진 그래프를 가지고 자식 노드들을 정리해야지 해당 쿼리에 해당하는 자식노드들을 셀 수 있다고 생각했다. 그래서 먼저 

그래프를 만들고, 자식 노드 갯수를 세는 방식으로 했는데 시간초과가 발생했다. 

어차피 루트 노드가 주어지므로, 루트 노드를 중심으로 뻗어나가면 자연스럽게 한 노드에 대한 자식노드가 정리 되기 때문에 굳이 트리를 만들지 않아도 된다 

이후 트리에서 마지막 입력받는 정점을 루트로하는 서브트리의 정점의 수를 출력하면 된다

dfs로 탐색하면서 각 정점에 대한 서브트리의 수를 count 배열에 담아준다

count배열로 방문여부 표시도 같이 해줄 수 있다 

참고한 블로그

-정답풀이:

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

N,R,Q=map(int,input().split())
graph=[[] for _ in range(N+1)]
size=[0]*(N+1)

for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def countPoint(x):
    size[x]=1
    for i in graph[x]:
        if not size[i]:
            countPoint(i)
            size[x]+=size[i]
countPoint(R)

for _ in range(Q):
    y=int(input())
    print(size[y])

-주의할점

graph=[[]*(N+1)]로 그래프를 초기화 했더니 IndexError가 발생했다. 찾아보니

이렇게 하면 graph=[[]]<- 이렇게 생겨서 값을 추가 할 수있는 인덱스가 없다. 

graph=[[] for _ in range(N+1)] 방식으로 작성하자!

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

풀이 없이 스스로 푼 문제. Silver Level1 문제이다. 탐색에는 특히 골드 문제가 많기 때문에 계속해서 탐색공부를 해야할 것 같다 

주의해야할 점이 세로가 m, 가로가 n이기 때문에 이것을 고려해서 풀어야한다

-정답풀이: 

처음에는 dfs로 풀었는데 틀려서 bfs로 바꿔서 풀고 맞힌 문제이다 

from collections import deque

def bfs(x,y,word):
    visit[x][y]=1
    cnt=1
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if not visit[nx][ny] and s[nx][ny]==word:
                    visit[nx][ny]=1
                    cnt+=1
                    q.append((nx,ny))
    return cnt

n,m=map(int,input().split()) 
s=[list(input()) for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*n for _ in range(m)]
white=0
blue=0

for i in range(m):
    for j in range(n):
        if not visit[i][j]:
            if s[i][j]=='W':
                ans=bfs(i,j,'W')
                white+=(ans**2)               
            elif s[i][j]=='B':
                ans=bfs(i,j,'B')
                blue+=(ans**2)
                
print(white,blue)

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

처음에는 한 값을 기준으로 dfs를 돌린 후 다음 값을 dfs 돌릴때 방문했던 노드를 방문하면 그것이 최소 공통조상이라고 생각하고 코드를 짰는데 계속 IndexError가 발생했다

그래서 그럼 각각의 부모노드들을 리스트로 만들어서 그것을 하나하나 비교하다가 처음으로 같은 것을 출력하면될 것이라고 생각했는데

이걸 dfs함수로 구현하면 각각 다른 리스트를 반환할텐데 그걸 어떻게 해야하나 싶은 생각이 들었다. global result같은 것을 못 쓸 것 같아서 찾아보니 그냥 while문으로 돌리고, 값을 하나씩 옮기는 식으로 진행하면된다 

그리고 최소 공통 부모는 각 리스트의 끝(루트노드)부터 내려와서 같지 않은 노드가 나올때까지 반복한 후, 처음으로 같지 않은 노드가 나왔을 때 노드의 부모가 최소공통조상이라고 할 수 있다

-정답풀이: 

t=int(input())
for _ in range(t):
    n=int(input())   
    graph=[0]*(n+1)
    for _ in range(n-1):
        a,b=map(int,input().split())
        graph[b]=a
    x,y=map(int,input().split())
    x_list=[x]
    y_list=[y]
    while graph[x]:
        x_list.append(graph[x])
        x=graph[x] #자식노드에서 부모노드로 이동
    while graph[y]:
        y_list.append(graph[y])
        y=graph[y]
    x_level=len(x_list)-1 #이 인덱스는 모두 루트 노드
    y_level=len(y_list)-1
    
    while x_list[x_level]==y_list[y_level]: 
        x_level-=1
        y_level-=1
    print(x_list[x_level+1])

-틀린풀이: 

def dfs(v):
    visit[v]=1
    for i in graph[v]:
        if visit[i]:
            print(i)
            exit()
        if not visit[i]:
            dfs(i)
            
t=int(input())
for _ in range(t):
    n=int(input())
    visit=[0]*(n+1)
    graph=[[]*(n+1)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        graph[b].append(a)
    x,y=map(int,input().split())
    dfs(x)
    dfs(y)

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

무한루프를 도는 조건이 사실 어떤 원리로 발생하는지 이해가 가지 않았다. 

찾아보니 방문했던 곳을 한번 더 방문하면 무한루프가 돌 가능성이 있어서 이것을 바탕으로 -1을 출력하면된다 

방문한 횟수를 dp 행렬을 따로 만들어 이용함으로써 시간초과를 방지할 수 있다고 한다 

마지막에 주의할 점은 ans값을 구했어도 마지막에 바깥으로 빠지거나 구멍에 빠질때도 한번 더 움직이는 것이므로 ans+1을 해주어야한다

참고한 블로그

-정답풀이:

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

n,m=map(int,input().split())
s=[list(map(str,input())) for _ in range(n)]
visit=[[0]*m for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

ans=0
dp=[[0]*m for _ in range(n)]
def dfs(x,y,cnt):
    global ans
    ans=max(ans,cnt)
    visit[x][y]=1
    k=int(s[x][y])
    for i in range(4):
        nx,ny=x+dx[i]*k,y+dy[i]*k
        if 0<=nx<n and 0<=ny<m and s[nx][ny]!='H' and cnt+1>dp[nx][ny]:
            if visit[nx][ny]:
                print(-1)
                exit()
            else:
                dp[nx][ny]+=1
                visit[nx][ny]=1
                dfs(nx,ny,cnt+1)
                visit[nx][ny]=0
dfs(0,0,0)
print(ans+1)