수학과의 개발자 도전기

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

Gold Level4 문제 

삼성 기출 문제이고, 이전에 한 번 풀어본 적이 있는데, 그때는 너무 어려워서 답만 베끼고 넘겼었다

이번에도 스스로 풀지는 못했지만, 그래도 최대한 풀이를 이해해보려고 했다 

며칠 뒤에 풀이 다시 한번 연습 해보려 한다 

참고한 블로그 

-정답 풀이 :

from collections import deque

sx,sy=0,0
shark_size=2
time=0
eat_cnt=0
fish_cnt=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]

n=int(input())
data=[]
for i in range(n):
    data.append(list(map(int,input().split())))
    for j in range(n):
        if 0<data[i][j]<=6:
            fish_cnt+=1
        if data[i][j]==9:
            sx,sy=i,j
data[sx][sy]=0

def bfs(x,y):
    q=deque()
    #상어 x,y,이동한 거리
    q.append((x,y,0))
    visit=[[0]*n for _ in range(n)]
    visit[x][y]=1
    distance=[]
    min_dist=10**9
    while q:
        x,y,dist=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n and not visit[nx][ny]:
                #상어가 이동할 수 있는 위치인지 확인 
                if data[nx][ny] <=shark_size:
                    visit[nx][ny]=1
                    
                    #먹을 수 있는 물고기가 있는 경우
                    #그 물고기 먹고 이동한 위치와 1칸 이동했으니 +1
                    if 0<data[nx][ny] < shark_size:
                        min_dist=dist
                        distance.append((dist+1,nx,ny))
                    #이동만 할 수 있는 경우
                    if dist+1 <= min_dist :
                        q.append((nx,ny,dist+1))
    if distance:
        distance.sort()
        #가장 가까운 먹을 수 있는 물고기 위치 반환 
        return distance[0]
    else:
        return False

while fish_cnt:
    result=bfs(sx,sy)
    
    if not result: 
        break
        
    sx,sy=result[1],result[2]
    time+=result[0]
    eat_cnt+=1
    fish_cnt-=1
    
    if shark_size == eat_cnt:
        shark_size+=1
        eat_cnt=0
    data[sx][sy]=0
    
print(time)

- 풀이 이해 :

처음에 상어 위치, 물고기 갯수 세는 거는 이해했으므로 패스 

현재 상어가 있는 위치에서부터 먹을 수 있는 가장 가까운 물고기의 위치를 찾는 탐색 로직이다. 

def bfs(x,y):
    q=deque()
    #상어 x,y,이동한 거리
    q.append((x,y,0))
    visit=[[0]*n for _ in range(n)]
    visit[x][y]=1
    distance=[]
    min_dist=10**9
    while q:
        x,y,dist=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n and not visit[nx][ny]:
                #상어가 이동할 수 있는 위치인지 확인 
                if data[nx][ny] <=shark_size:
                    visit[nx][ny]=1
                    
                    #먹을 수 있는 물고기가 있는 경우
                    #그 물고기 먹고 이동한 위치와 1칸 이동했으니 +1
                    if 0<data[nx][ny] < shark_size:
                        min_dist=dist
                        distance.append((dist+1,nx,ny))
                    #이동만 할 수 있는 경우
                    if dist+1 <= min_dist :
                        q.append((nx,ny,dist+1))
    if distance:
        distance.sort()
        #가장 가까운 먹을 수 있는 물고기 위치 반환 
        return distance[0]
    else:
        return False

먹을 수 있는 물고기가 있을 때까지 루프를 돌린다. 

bfs로 현재 상어가 있는 위치에서 먹을 수 있는 가장 가까운 물고기의 위치와 거기까지의 거리를 받는다 

sx,sy까지의 거리가 곧 가는데 걸리는 시간이므로 dist(result[0])을 time에 더해주고, 먹은 물고기 +1, 물고기 갯수 -1 을 해준다 

이부분이 잘 이해가 가지 않는데, 먹은 물고기 개수와 상어의 크기가 같으면 상어의 크기를 +1 한다???

if shark_size == eat_cnt:
        shark_size+=1
        eat_cnt=0

while fish_cnt:
    result=bfs(sx,sy)
    
    if not result: 
        break
        
    sx,sy=result[1],result[2]
    time+=result[0]
    eat_cnt+=1
    fish_cnt-=1
    
    if shark_size == eat_cnt:
        shark_size+=1
        eat_cnt=0
    data[sx][sy]=0
    
print(time)

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

스스로 푼 문제다! Silver Level2 문제 

처음에 bfs로 풀었는데, 잘 안돼서 dfs로 변경 후 진행했더니 정답이 떴다. 

로직은 탐색을 하면서 v번째 리스트에 있는 원소들의 루트는 v이므로, root 리스트에 이를 입력해 주고, 

탐색 여부는 visit 안 한 원소들로만 진행한다(not visit)

recursionError가 발생해서 sys.setrecursionlimit(10**6)을 걸어줬다 

그리고 초반에 작성했던 bfs풀이도 정답이 떴지만, 시간이 오래 걸렸다 

- 정답 풀이 :

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

n=int(input())
data=[[] for _ in range(n+1)]
root=[0]*(n+1)
visit=[0]*(n+1)
visit[0]=1
visit[1]=1
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
    
def dfs(v):
    visit[v]=1
    for i in data[v]:
        if not visit[i]:
            visit[i]=1
            root[i]=v
            dfs(i)
 
dfs(1)
for i in range(2,n+1):
    print(root[i])

-BFS 풀이 

sys.stdin.readline으로 하면 안 할 때보다 시간이 1/10로 단축된다 

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

n=int(input())
data=[[] for _ in range(n+1)]
root=[0]*(n+1)
visit=[0]*(n+1)
visit[0]=1
visit[1]=1
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
    
def bfs(v):
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if not visit[i]:
                visit[i]=1
                root[i]=x
                queue.append(i)
bfs(1)            
for i in range(2,n+1):
    print(root[i])

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

스스로 푼 문제다 ! Gold Level5 문제 

처음에는 적록색약이 아닌 사람에 대한 bfs와 적록색약인 사람에 대한 bfs를 따로 만들어줘야하나 고민이 됐다. 

일단 적록색약이 아닌 경우는 그동안 해온 bfs로 하면 되는데, 문제는 적록색약인 사람은 R과 G이 같게 인식돼 R에서 G로 갈 수도, G에서 R로 갈 수도 있는데 이를 어떻게 구현해야할지 몰랐다. 

일단 되는대로 bfs 두개 만들어서 돌렸는데 틀렸다. 그래서 갑자기 생각난게 적록색약 아닌 경우 진행한 다음에 R과 G의 값을 하나로 치환한뒤 같은 bfs 돌리면 갯수 나오겠다 싶어서 그렇게 돌렸더니 정답이 떴다. 

처음에 풀었을 때는 엄청 헤맸는데, 두번째 풀이 때는 스스로 풀어서 뿌듯하다

- 정답 풀이 :

from collections import deque
n=int(input())
data=[]
for _ in range(n):
    data.append(list(input()))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
one,two=0,0

def bfs(x,y,letter):
    queue=deque()
    queue.append((x,y))
    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<n:
                if not visit[nx][ny] and data[nx][ny]==letter:
                    visit[nx][ny]=1
                    queue.append((nx,ny))
                    
visit=[[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            bfs(i,j,data[i][j])
            one+=1

#적록색약은 적색과 녹색이 같게 보이므로, 둘을 같은 문자로 치환해준다            
for i in range(n):
    for j in range(n):
        if data[i][j]=='R' or data[i][j]=='G':
            data[i][j]='K'
            
visit=[[0]*n for _ in range(n)]            
for i in range(n):
    for j in range(n):
        if not visit[i][j] :
            bfs(i,j,data[i][j])
            two+=1
            
print(one,two)

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

- 정답 풀이 : 

이전에 풀었던 토마토와 풀이는 비슷한데, 3중 행렬이라 약간 다르다. 

이거는 리스트 하나만 더 추가한 뒤 그거에 맞춰서 진행해주면 된다 

스스로 푼 문제!! Gold Level 5 문제다 

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

n,m,h=map(int,input().split())
data=[[] for _ in range(h)]
tomato=deque()
flag=False

for i in range(h):
    for j in range(m):
        data[i].append(list(map(int,input().split())))
        for k in range(n):
            if data[i][j][k]==1:
                tomato.append((i,j,k))
            if data[i][j][k]==0:
                flag=True
                
direct=[[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]]                

def bfs():
    while tomato:
        a,b,c=tomato.popleft()
        for i in range(6):
            na,nb,nc=a+direct[i][0],b+direct[i][1],c+direct[i][2]
            if 0<=na<h and 0<=nb<m and 0<=nc<n:
                if data[na][nb][nc]==0:                   
                    data[na][nb][nc]=data[a][b][c]+1
                    tomato.append((na,nb,nc))
bfs()

if not flag:
    print(0)
else: 
    minNum,maxNum=10**9,0
    for i in range(h):
        for j in range(m):
            if 0 in data[i][j]:
                minNum=0                
            else: 
                maxNum=max(max(data[i][j]),maxNum)
    if minNum==0:
        print(-1)
    else:
        print(maxNum-1)