수학과의 개발자 도전기

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

-정답풀이:

direction=[(-1,0),(1,0),(0,-1),(0,1)]으로 방향 이동하는 리스트 구현하기 

visit.pop() 구현하기 

n번만큼 주어진 확률*100이 곱해졌을 것이므로 (0.01**n)을 ans에 곱해서 출력해주기 

def dfs(x,y,cnt,visit):
    global ans   
    if len(visit)==n+1:
        ans+=cnt
        return ans
        
    for i in range(4):
        nx,ny=x+direction[i][0],y+direction[i][1]
        if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,cnt*probability[i],visit)
            visit.pop()
            
n,E,W,S,N=(map(int,input().split()))
probability=[E,W,S,N]
direction=[(-1,0),(1,0),(0,-1),(0,1)]

ans=0
dfs(0,0,1,[(0,0)])

print(ans*((0.01)**n))

-처음 풀이: 

고쳐야할 점이 많은 코드이다

1. 먼저 방문한 위치를 어떻게 표현해야할지 몰랐다(문제에서 로봇은 행렬위에서 움직이는 게 아니라는 생각에 어떻게 표현해야하는지 몰랐는데, 그냥 이동하는 좌표를 하나씩 visit에 추가해주면 된다는 것을 알았다)

2. 하나의 깊이로 이동하기 때문에 중간에 ans+=cnt 코드가 있으면 cnt의 값이 계속해서 축적돼서 정확한 ans 값이 나오지 않는다 

그래서 dfs함수를 나올때 ans +=cnt를 해줘야한다 

3. probability[i] !=0 은 굳이 필요없는 코드이다 

4. 처음 숫자 input()할 때, n,e,w,s,n에서 n이 중복되므로 둘 중에 하나를 다른 문자로 변경했어야했다. 이거 발견 못해서 몇번이나 시간초과가 발생했다 

def dfs(x,y,cnt,n):
    #방문처리(위치를 어떻게 표현해야할지 몰랐다)
    global ans
    ans+=cnt
    if n==0: 
    	return ans
        
    for i in range(4):
        if probabilty[i]!=0 and not visit:
            if direction[i]=='E':
                dfs(x+1,y,cnt*probability[i],n-1)
            if direction[i]=='W':
                dfs(x-1,y,cnt*probability[i],n-1)
            if direction[i]=='S':
                dfs(x,y+1,cnt*probability[i],n-1)
            if direction[i]=='N':
                dfs(x,y-1,cnt*probability[i],n-1)
            
n,e,w,s,n=(map(int,input().split()))/100
n=n*100
probability=[e,w,s,n]
direction=['E','W','S','N']
ans=0
dfs(0,0,1,n)
print(ans)

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

이진트리의 순회 방법을 처음 접해서 어떻게 풀어야할지 몰랐던 문제다

문제의 접근법은 중위순회이다. 

중위순회를 하면서 각 레벨에 따라 거리를 저장하는 것이 중요하다 

중위 순회란?

: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 순회. 노드->부모노드->형제노드 순서로 진행하고,

예시로는 수식트리가 있다 

(1) 왼쪽 하위 트리부터 시작 : 가장 왼쪽의 '잎 노드'부터 시작한다는 말

(2) 루트

(3) 오른쪽 하위 트리 

-정답풀이: 

import sys
input=sys.stdin.readline

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

#루트 확인하는 리스트
isRoot=[0]*(n+1) 
root=0

#거리값 저장하는 리스트
distance=[[] for _ in range(n+1)] 


for _ in range(n):
    parent,left,right=map(int,input().split())
    graph[parent].append(left)
    graph[parent].append(right)
    isRoot[parent]+=1
    if left !=-1:
        isRoot[left]+=1
    if right !=-1:
        isRoot[right]+=1

#루트 설정하기        
for i in range(1,n+1):
	#루트를 제외한 노드는 isRoot==2이다 
    if isRoot[i]==1:
        root=i
        
num=1
def inorder(start,deep): #deep은 레벨에 관련된 값, num은 거리에 관련된 값
    global num
    #왼쪽자식노드에 자식이 있을때
    if graph[start][0]!=-1: 
    	#왼쪽자식노드로 dfs진행 &깊이+1
        inorder(graph[start][0],deep+1)
    #해당 레벨(deep)에 해당하는 거리 삽입
    distance[deep].append(num) 
    num+=1 #이 라인이랑 위 라인만 이해가 가지 않는다#
    if graph[start][1]!=-1:
        inorder(graph[start][1],deep+1)
        
inorder(root,1)
level=1
ans=max(distance[1])-min(distance[1])+1
for i in range(2,n+1):
    if distance[i]:
        small=min(distance[i])
        large=max(distance[i])
        if ans<large-small+1:
            ans=large-small+1
            level=i
print(level)
print(ans)

-가장 이해가 가지 않는 부분:

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

당최 무슨말인지 잘 모르겠는 문제다,, 

다시 공부해야겠다 

참고한 블로그 ​

-정답풀이:

import sys
from itertools import combinations
from collections import deque
input=sys.stdin.readline
n=int(input())
people=list(map(int,input().split()))
arr=[[0]*n for _ in range(n)]

for i in range(n):
    _,*dsts = map(int,input().split())
    for dst in dsts:
        arr[i][dst-1]=1
        
def bfs(nodes):
    q=deque()
    q.append(nodes[0])
    check=[False for _ in range(n)]
    check[nodes[0]]=True
    
    while q:
        node=q.popleft()
        for i in range(len(arr[node])):
            if arr[node][i]==0: continue
            if i not in nodes: continue
            if not check[i]:
                check[i]=True
                q.append(i)
    return check.count(True)== len(nodes)

def get_total(nodes):
    total=0
    for node in nodes:
        total+=people[node]
    return total

cases=[]
x={i for i in range(n)}
INF=int(1e9)
ans=INF

for i in range(1, n//2+1):
    As=tuple(combinations(x,i))
    for A in As:
        B=list(x.difference(A))
        
        if bfs(A) and bfs(B):
            a_total= get_total(A)
            b_total= get_total(B)
            ans= min(ans, abs(a_total-b_total))
            
if ans==INF: print(-1)
else: print(ans)

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

처음에는 bfs로 풀어야할 것 같아 풀어보려고 했으나 depth를 구하기 어려울 것 같아서 dfs로 풀어야되겠다고 생각했다 

이동하는 것까지는 구현하겠는데, 탈출 조건을 어떻게 해야할지 몰랐다. 

탈출조건으로 생각한게 주변에 있는 문자들이 모두 result에 있는 문자들이면 반환되는 것을 생각했다. 이렇게 탈출한 result의 길이를 구하면된다고 생각했지만 틀린 생각이었다 

dfs는 x,y,cnt 3가지의 파라미터로 진행을 한다. x,y는 2차원 행렬에서의 위치를 의미하고, cnt는 depth를 의미하는 것 같다 

앞으로 깊이를 구하는 문제에서 cnt 파라미터를 추가해서 진행해야겠다고 생각했다 

여기서 global ans를 선언해서 (x,y)까지의 깊이 중 최댓값을 저장한다 

result.remove(s[nx][ny])가 중요한데, 만약 최대 칸 수가 아닌 경우 돌아가기 위해서이다(백트래킹 과정)

함수를 시작하기 위한 초기값을 result에 추가하고 dfs를 진행한다 

-정답풀이: 

r,c=map(int,input().split())
s=[list(input()) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
result=set()
ans=0
def dfs(x,y,cnt):    
    global ans
    ans=max(ans,cnt)
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<r and 0<=ny<c:
            if s[nx][ny] not in result:
                result.add(s[nx][ny])
                dfs(nx,ny,cnt+1)
                result.remove(s[nx][ny])
                
result.add(s[0][0])                                                      
dfs(0,0,1)
print(ans)