수학과의 개발자 도전기

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

-틀린풀이: 

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

어려운 문제는 아니었는데 각 루트 노드에서 시작하기 때문에 visit를 하면 안된다고 생각했지만 하나의 루트 당 이전에 들린 노드는 표시를 해야하므로 bfs단위로 visit를 설정해야한다는 것을 배웠다 

그리고 블로그 따라서 똑같이 했는데 자꾸 typeerror, indexerror가 난다.,, 짜증

-정답풀이:

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    q = deque()
    q.append(start)
    visit = [0 for _ in range(n + 1)]
    visit[start] = 1
    cnt = 1
    while q:
        st = q.popleft()
        for i in s[st]:
            if visit[i] == 0:
                visit[i] = 1
                cnt += 1
                q.append(i)
    return cnt
    
n, m = map(int, input().split())
s = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    s[b].append(a)
    
result = []
max_cnt = 0
for i in range(1, n + 1):
    tmp = bfs(i)
    if max_cnt == tmp:
        result.append(i)
    if max_cnt < tmp:
        max_cnt = tmp
        result = []
        result.append(i)
        
print(*result)

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

bfs를 그래프나 행렬로만 접했어서 어떻게 접근해야할지 잘 몰랐던 문제다. 

찾아보니 물통의 크기에 따라 따를 수 있는 모든 경우의 수를 구하는 것을 bfs로 진행해야한다고 한다

a,b,c에 담겨있는 물의 양을 x,y,z라고 한다면 

x를 b에 담을 때 두 가지의 경우가 있다. 

1. x를 모두 b에 담는경우(x가 b-y보다 더 작다면 x를 모두 b에 부을 수 있다 )

2. b가 꽉 차는 경우(만약 b-y(b에 남은 공간)가 x보다 작으면 x를 다 따르지 못하고 b만 꽉 찬다)

=> water=min(x,b-y)

위와 같은 방식으로 x를 기준으로,y를 기준으로,z를 기준으로 if문을 작성한 후 pour를 해주면 된다 

x&(b,y), x&(c,z), y&(a,x), y&(c,z), z&(a,x), z&(b,y) 총 여섯가지의 if문이 생성된다 

if문을 다 작성한 뒤 pour에 파라미터를 넣을 때 조심해야한다. pour에 들어가는 파라미터는 a의 용량 변화한거와 b의 용량 변화한거를 넣어야한다 

-정답풀이:

from collections import deque

#x는 a에 담긴 물의 양,y는 b에 담긴 물의 양
def pour(x,y):
    if not visit[x][y]:
        visit[x][y]=1
        queue.append([x,y])
        
def bfs():
    queue=deque()
    queue.append((0,0))
    visit[0][0]=1
    while queue:
        x,y=queue.popleft()
        z=c-x-y #처음에 c에만 물이 있었으므로 x,y값 빼면 c에 담긴 물의 양 
        
        #문제에서 주어진 조건이 첫 번재 물통이 비어 있을 때, 세 번째 물통에 담겨있을 수 있는 물의 양 구하는 것임
        if x==0:
            ans.append(z)
            
        if x>0 and b>y:
            water=min(x,b-y)
            #A에서 B로 물 이동(B 꽉 채움)
            pour(x-water,y+water)
        if x>0 and c>z:
            water=min(x,c-z)
            #A에서 C로 물 이동(C 꽉 채움)
            pour(x-water,y) #b에서의 변화는 없으므로
            
        if y>0 and a>x:
            water=min(y,a-x)
            #B에서 A로 물 이동(A 꽉채움)
            pour(x+water,y-water)
        if y>0 and c>z:
            water=min(y,c-z)
            #B에서 C로 물 이동(C 꽉채움)
            pour(x,y-water)
            
        if z>0 and a>x:
            water=min(z,a-x)
            #C에서 A로 물 이동(A 꽉 채움)
            pour(x+water,y)
        if z>0 and b>y:
            water=min(z,b-y)
            #C에서 B로 물 이동(B 꽉 채움)
            pour(x,y+water)
            
a,b,c=map(int,input().split())
ans=[]
visit=[[0]*(b+1) for _ in range(a+1)]

bfs()

ans.sort()
for i in ans :
    print(i,end=' ')

풀면서 범했던 실수들

1) 띄어쓰기 오류(Indentation오류)

2)오타: for i in range ans: -> for i in ans:

3)출력할 때 숫자 간 간격 띄우기(문제 출력 조건 만족하게 작성하기): print(i,end='') ->print(i,end=' ') 

4)queue에 (0,0) 두번 삽입,,,