수학과의 개발자 도전기

-문제: 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) 두번 삽입,,,

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

29번 라인 빼고 나머지는 스스로 작성한 코드이다. 

풀면서 계속 valueError를 마주쳤는데, 해당 에러를 발생한 코드를 기록하려고 한다 

-정답풀이:

풀이는 다른 bfs문제들과 비슷했던 것 같다 

방문하지 않고, 값이 1인 것들을 기준으로 bfs를 실행하고, 실행하면서 해당 그림의 크기를 잴 수 있게 cnt라는 변수를 계산하고 반환했다. 

실수한 부분(실수한 부분을 인지해서 같은 것을 반복하게 하지 않기 위함):

1)처음에 cnt=0으로 선언했어서 틀렸다. 

그런데 bfs가 시작 되었을 때는 1이 하나 있으므로 cnt=1로 시작해야한다 

2) 오타부분 graph를 grpah로 작성하거나, 

graph[i][j]라고 입력해야하는 것을 graph[nx][ny]라고 입력했다 

from collections import deque

dx=[-1,1,0,0]
dy=[0,0,-1,1]

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

n,m=map(int,input().split())
visit=[[0]*m for _ in range(n)]
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
    
ans=0
result=0
for i in range(n):
    for j in range(m):
        if visit[i][j]==0 and graph[i][j]==1:
            result=max(bfs(i,j),result)
            ans+=1           
print(ans)
print(result)

-틀린풀이: 

반환되는 값들이 정수라고 생각해 그들을 리스트에 삽입한 후 그 중에서 가장 큰 값을 출력하는 것을 생각했는데 계속해서 ValueError가 발생했다. 이 외의 코드는 정답풀이와 동일하다 

(2022.08.02)

result에 아무 원소도 없을 때 max([])의 형태인데, 리스트는 들어왔지만, 안에서 최댓값을 찾을 수 있는 게 없어서 ValueError가 발생했다

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

1. 공기와 접촉하면 천천히 녹는다. 내부에 있는 공간은 접촉하지 않는 것으로 가정한다. 이 의미에 힌트가 있다

2. 내부에 있는 공간은 접촉하지 않으므로 외부에서부터 bfs로 진행해줘서 2번이상 접촉을 하면 다음 반복문에서 제외시켜주면 된다

3. 마지막으로 전체가 0일 때 무한루프를 탈출해준다 

-정답풀이: 

from collections import deque

n,m=map(int,input().split())
cheeze=[list(map(int,input().split())) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
time=0
while True:
    q=deque()
    ch=[[0]*m for _ in range(n)]
    ch[0][0]=1
    q.append([0,0])
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m and not ch[nx][ny]:
                #치즈가 있는 곳
                if cheeze[nx][ny]:
                	#그 치즈와 접하는 공기면 갯수 추가
                    cheeze[nx][ny]+=1 
                #치즈가 없는 곳
                else: #cheeze[nx][ny]==0 
                	#공기가 지나갔다는 표시
                    ch[nx][ny]=1 
                    q.append((nx,ny))
    flag=0
    for i in range(n):
        for j in range(m):
            if cheeze[i][j]>=3:#공기 2면과 닿은 치즈는 없어진다
                cheeze[i][j]=0
            elif 0< cheeze[i][j]:
                flag=1
                cheeze[i][j]=1
    time+=1
    if not flag: #flag가 0일 때 
        print(time)
        break

-풀이 이해:

방문하지 않은 곳을 기준으로 치즈가 있는 영역이면 +1 해준다

방문하지 않은 곳인데 치즈가 없다면 방문 표시만 하고, 해당 위치로 이동한다

elif cheeze 값이 1 또는 2일 경우 공기와 닿는면이 없거나 한변 밖에 없다

flag가 1이면 아직 사라지지 않은 치즈가 있다는 말이라서 계속 시간을 재면된다 

flag==0이면 치즈가 모두 사라졌다는 의미이므로 time을 출력해준다 

Q: 그럼 치즈가 없는 곳을 기준으로 이동한다는 말인가?