수학과의 개발자 도전기

-문제: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: 그럼 치즈가 없는 곳을 기준으로 이동한다는 말인가? 

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

Gold level 5문제다 

문제를 이해한 것으로는 1. 노드를 없애고 2. 자식 노드를 구별해서 그것의 갯수를 구해야한다고 생각했다. 

1번을 구체적으로 하자면

처음 지운 노드의 모든 자식노드들도 삭제되어야 하므로 그들의 인덱스 값에 -2를 대입해야하는데, 이때 dfs를 사용해야한다고 생각했다.

-2를 넣은 이유는 -1은 루트 노드를 가리키기 때문에 다른 숫자로 삭제 노드를 표현해야 했다 

배열 전체를 탐색하며, 방금 삭제한 인덱스를 부모로 가지는 노드를 찾아 dfs함수를 재귀호출한다 

2번을 구체적으로 하자면 

dfs로 노드들을 삭제한 뒤 삭제되지 않고 남은 트리에서 자식노드를 구해서 그것의 갯수를 구하면 된다 

이 문제에서 나는 1번을 구현하는 것이 어려웠던 것 같다. 2번은 비교적 쉬웠다 

-정답풀이: 

n=int(input())
s=list(map(int,input().split()))
k=int(input())

#k노드 지우고 트리 정리
def dfs(v,s):
    s[v]=-2
    for i in range(n):
        if v==s[i]: #v가 부모노드일때
            dfs(i,s) #v의 자식노드들도 삭제하기 
        

dfs(k,s)     
cnt=0        
for i in range(n):
    if s[i]!=-2 and (i not in s):
        cnt+=1
print(cnt)

-틀린 풀이 피드백:

dfs에서 초기값을 넣으면 그 값부터 -2로 바뀐 후 진행되므로 15-19라인은 굳이 필요 없었다. 이 내용을 dfs 구현 내용에 넣으면 된다(물론 둘다 코드는 틀렸다)

그리고 22-25라인은 필요 없다. 왜냐하면 이미 주어진 리스트 s의 값들이 부모노드를 의미하므로 굳이 parent라는 리스트를 따로 만들어서 값을 넣을 필요는 없다 -2가 아니면 다 부모 노드이므로.

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

Gold level3 문제이다 

문제에서 팀을 이루는 경우는 두가지 인데, 

1) 자기 자신과 팀을 이루는 경우

2) 두명이상이고, 사이클을 이루는 경우

위 두 상황은 별개라고 생각해서 1)번을 특히 어떻게 구현해야 할지 잘 몰랐는데 1)번 경우도 사이클을 이루는 경우 이므로 

결과적으로 cycle을 이루는 것에 대해서만 함수를 작성하면 된다는 것을 구글링을 통해 알았다 

사이클이 되는 조건: 첫번째수 == 마지막 수가 가리키는 숫자

예) 4-7, 7-6, 6-4는 사이클을 이룬다. 6이 가리키는 숫자가 처음 시작인 4이기 때문

-정답풀이: 

import sys
sys.setrecursionlimit(111111)

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)
        
for _ in range(int(input())):
    n=int(input())
    s=[0]+list(map(int,input().split()))
    visit=[1]+[0]*n
    result=[]
    for i in range(1,n+1):
        if not visit[i]:
            cycle=[]
            dfs(i)
    print(n-len(result))

-풀이 이해:

def dfs(v):
    global result
    visit[v]=1
    cycle.append(v)#사이클을 이루는 팀을 확인하기 위해
    number=s[v]
    if visit[number]:
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룬다
        return 
    else:
        dfs(number)

10번에 if number in cycle: 이 의미하는 것은 마지막 숫자가 가리키는 숫자가 cycle이라는 리스트 안에 있다면 그건 cycle을 이룬다는 것이다

그래서 number가 사이클의 시작이므로 number의 인덱스 부터 끝까지의 리스트를 result에 추가한다

사이클을 이루지 않는 경우는 다음 dfs를 실행하면 된다