수학과의 개발자 도전기

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

깊이가 4인 노드를 찾는 문제라고 생각한 후 그렇게 작성해봤는데, 생각보다 쉽지 않았던 문제 

탐색을 진행한 다음에 visit를 왜 0 처리 하는지 모르겠다 

- 정답 풀이 :

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

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

data=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)

def dfs(v,depth): 
    global flag
    visit[v]=1
    if depth==4:
        flag=True
        return flag
    for x in data[v]:
        if not visit[x]:
            dfs(x,depth+1) 
            visit[x]=0 #여기
    return False   

flag=False
visit=[0]*n #여기           
for i in range(n):
    dfs(i,0)
    visit[i]=0 #여기
    if flag:
        break
if flag:
    print(1)
else:
    print(0)

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

첫 번째 풀었을 때는 정답보고 30회 가량 시도했는데도 계속 안됐던 것 같은데 

이번엔 비교적 쉽게 푼 느낌이다 

자식노드를 중심으로 진행하고, 하나의 노드마다 방문한 노드 수를 리스트 인덱스에 저장한 뒤, 그 중에 최댓값을 가진 인덱스들을 오름차순으로 출력하는 걸로 이해했다 

visit 인덱스마다 진행한 깊이를 진행하려고했는데, 이렇게 하니까 메모리 초과가 발생했다 

그래서 풀이를 봤더니 visit는 매 노드마다 초기화하고, 다른 리스트에 각 노드의 깊이를 저장해서 진행하는 것 같아서 

그렇게 변형했더니 정답이 떴다 

시간이 꽤 오래걸렸던 문제다 

- 정답 풀이 : 

from collections import deque

n,m=map(int,input().split())
data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[b].append(a)

def bfs(v):
    visit=[0]*(n+1)
    visit[v]=1
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if not visit[i]:
                visit[i]=1
                count[v]+=1
                queue.append(i)                   

count=[0]*(n+1)
result=0
for i in range(1,n+1):
    bfs(i)
    result=max(result,max(count))
    
for i in range(1,n+1):
    if count[i]==result:
        print(i, end = ' ')

- 이렇게 풀면 메모리 초과난다(방문한 노드 처리 안 해줘서)

from collections import deque

n,m=map(int,input().split())
data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[b].append(a)

def bfs(v):
    visit[v]=1
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        if len(data[v])!=0:
            for i in data[x]:
                visit[v]+=1
                queue.append(i)                   

visit=[0]*(n+1)
answer=''
result=0
for i in range(1,n+1):
    bfs(i)
    result=max(result,visit)
    
for i in range(1,n+1):
    if visit[i]==result:
        print(i, end = ' ')

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

내부 로직은 맞았는데, 결과 출력할 때 잘못 작성해서 53%에서 계속 틀렸다. 

조건에 따라 bfs로 넓이를 구한뒤 그 값을 reulst=[]에 삽입해서 그것의 갯수와 최댓값을 구하는 로직을 짰는데

내가 봤을 땐 result=[]일 때 에러가 생겼던 것 같다 

그래서 이 부분을 result=0으로 바꾸고, bfs 실행할 때마다 max로 값 비교를 한 후 출력하니 정답이 떴다 

- 정답 풀이 :

from collections import deque

n,m=map(int,input().split())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
visit=[[0]*m for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]    
          
def bfs(x,y):
    queue=deque()
    queue.append((x,y))   
    count=1        
    while queue:
           x,y=queue.popleft()
           for i in range(4):
               nx,ny=x+dx[i],y+dy[i]
               if 0<=nx<n and 0<=ny<m:
                if visit[nx][ny] ==0 and data[nx][ny]==1:
                    visit[nx][ny]=1
                    count+=1
                    queue.append((nx,ny))
    return count

result=0
answer=0
for i in range(n):
    for j in range(m):
        if visit[i][j] ==0  and data[i][j]==1:
            visit[i][j]=1
            result=max(result,bfs(i,j))
            answer+=1

print(answer)
print(result)

-틀렸던 부분

result=[]  
answer=0
for i in range(n):
    for j in range(m):
        if visit[i][j] ==0  and data[i][j]==1:
            visit[i][j]=1
            result.append(bfs(i,j))
            answer+=1

if len(result)==0:
    print(0)
else:    
    print(answer)           
    print(max(result))

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

리스트 트리 구조로 바꾸고, visit 리스트 추가해서 진행했더니 메모리초과가 떠서 실패했던 문제 

굳이 이렇게 할 필요 없고, 주어진 리스트에 삭제된 노드 -2 처리하고, 리스트 값에 없는 값들이 자식 노드이므로 

자식노드이고, -2 처리가 안 된 인덱스 갯수를 센 후 출력하면 된다 

- 정답 풀이 : 

import sys
sys.setrecursionlimit(10**6)

n=int(input())
data=list(map(int,input().split()))
target=int(input())

def dfs(x,data):  
    data[x]=-2
    for i in range(n):
        if x==data[i]:
            dfs(i,data)
        
dfs(target,data)

count=0
for i in range(n):
    #삭제 되지 않은 자식 노드
    if data[i]!=-2 and (i not in data):
        count+=1
        
print(count)