수학과의 개발자 도전기

-문제: 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)

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

쉬운 문제인데 구현할게 많았던 문제

하나의 영역을 탐색할 때 늑대의 수와 양의 수를 구한뒤 해당 영역에서 양의 수 > 늑대 수 라면 해당 영역의 늑대수 만큼 없애는 것이라고 생각해서 하나의 영역을 탐색한 수 양과 늑대의 수를 각각 반환한 뒤 그거를 비교해서 쌓는 것으로 생각했는데 계속해서 에러가 나와서 구글링을 한 뒤 다음과 같은 코드를 작성했다 

-정답풀이:

먼저 전체 늑대수와 전체 양의 수를 구한 뒤, 조건에 맞춰서 늑대의 수를 줄이거나, 양의 수를 줄이는 방식으로 해야한다 

처음 구한 전체 값은 지역변수로 할당해준다(global)

from collections import deque

def bfs(x,y):
    visit[x][y]=1
    q=deque()
    q.append((x,y))
    result=[]
    global o,v
    wolf,sheep=0,0
    if s[x][y]=='v': wolf+=1
    elif s[x][y]=='o': sheep+=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<r and 0<=ny<c and not visit[nx][ny] and s[nx][ny]!='#':
                visit[nx][ny]=1
                q.append((nx,ny))                                                      
                if s[nx][ny]=='v':                                        
                    wolf+=1
                if s[nx][ny]=='o':                   
                    sheep+=1
    if wolf and sheep:
        if sheep > wolf:
            v-=wolf
        else:
            o-=sheep 
            
r,c=map(int,input().split())
s=[]
o,v=0,0
for _ in range(r):
    a=list(input().strip())
    for j in range(c):
        if a[j]=='o': o+=1
        if a[j]=='v': v+=1
    s.append(a)                
            
visit=[[0]*(c) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(r):
    for j in range(c):
        if not visit[i][j] and s[i][j]!='#':
            bfs(i,j)
            
print(o,v)

-틀린풀이

from collections import deque

def bfs(x,y):
    visit[x][y]=1
    q=deque()
    q.append((x,y))
    result=[]
    wolf,sheep=0,0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<r and 0<=ny<c and not visit[nx][ny] and s[nx][ny]!='#':
                visit[nx][ny]=1
                if s[nx][ny]=='.':
                    q.append((nx,ny))                  
                if s[nx][ny]=='v':
                    q.append((nx,ny))                    
                    wolf+=1
                else:
                    q.append((nx,ny))
                    sheep+=1
    if sheep>wolf:
        wolf=0
    else: 
        sheep=0
    return result.append((sheep,wolf))                 
r,c=map(int,input().split())
s=[]
for _ in range(r):
    s.append(list(map(str,input())))
    
visit=[[0]*(c) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
ans=0
cnt=0
for i in range(r):
    for j in range(c):
        if not visit[i][j] and s[i][j]!='#':
            bfs(i,j)
            ans+=result[0]
            cnt+=result[1]
print(ans,cnt)

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

문제를 읽고 무슨 말을 하는지 잘 몰랐다 

그래서 에제4를 살펴보니 3-4-6 이렇게 있길래 친구가 연결되는 게 있으면 1을 출력하고 아니면 0을 출력하는 건가? 생각하고 다음과 같은 코드를 작성했다

25%에서 틀리길래 뭐가 문제인지 찾아봤는데 문제를 아예 잘못 이해하고 있었다 

abcde의 관계처럼 깊이가 4인 트리가 있는지 찾아보는 문제였다

그리고 이 문제에서는 노드가 0부터 시작하기 때문에 graph부터,visit, range에 들어가는 값 모두 n으로 설정해야한다  

-정답풀이: 

import sys

n,m=map(int,input().split())

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

-틀린풀이: