Coding 공부

from collections import deque

def bfs(x):
    queue = deque()
    queue.append(x)
    distance[x] = 0
    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if visited[next_node] == False:
                visited[next_node] = True
                if distance[next_node] == -1:
                    distance[next_node] = distance[now] + 1
                    queue.append(next_node)
                
                

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

distance = [-1] * (n + 1)
visited = [False] * (n + 1)

bfs(x)

result = []
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        result.append(i)
        check = True
if len(result):
    for i in range(len(result)):
        print(result[i])
else:
    print(-1)

 기초적인 다익스트라 문제이고, 다익스트라를 모르더라도 BFS를 아는 것만으로 풀 수 있다.

이 문제를 풀 시기에 다익스트라를 몰랐고, 현재도 다익스트라를 배웠지만 자주 안 쓰다보니 까먹었다!(다시 공부해야한다.)

이 문제는 단 방향 그래프이고, 방문 여부와 거리를 저장하기 위한 리스트를 만들어주었다.

bfs 를 통해 현재 위치에서 최단거리를 구하고, 이동거리를 저장하고 주어진 K와 같은 노드들을 출력해주면 된다.

T = int(input())

dx = [-2,-1,1,2,2,1,-1,-2]

dy = [-1,-2,-2,-1,1,2,2,1]

for tc in range(T):

    l = int(input())

    array = [list(map(int,input().split())) for _ in range(2)]



    start = array[0][:]

    end = array[1][:]

    if start == end:

        print(0)

    else:

        result = 0

        visited = [[0]*l for _ in range(l)]

        visited[start[0]][start[1]] = 1

        stack = []

        stack.append((start[0],start[1],0))

        while stack:

            x,y,cnt = stack.pop(0)

            if x == end[0] and y == end[1]:

                result = cnt

                break

            for i in range(8):

                nx = x + dx[i]

                ny = y + dy[i]

                if 0<=nx<l and 0<=ny<l:

                    if not visited[nx][ny]:

                        visited[nx][ny] = 1

                        stack.append((nx,ny,cnt+1))

        print(result)

BFS를 이용해서 거리 변수만 추가해주면 되는 문제였다.

# 16236번 아기상어
# N*N 크기에 물고기 M마리 아기상어 1마리
# 아기상어 초기 크기는 2,
# 자기보다 큰 물고기는 먹기x 지나가기 x
# 자기와 같은 물고기 먹기x, 지나가기 o
# 자기보다 작은 물고기 먹기 o 지나가기 o
# 아기상어는 자기 크기 만큼의 횟수만큼 물고기를 먹는다면 크기가 1 증가한다.
# 먹을 수 있는 물고기가 없으면 엄마상어에게 가기
# 먹을 수 있는 물고기가 1마리면 거리가 가장 가까운 물고기를 먹으러간다.
# 먹을수 있는 물고기가 가장 가까운 거리에 있는걸 먹는다. 위 1순위 왼쪽 2순위 위로 정렬 왼쪽으로 정렬 2중정렬
# 1~6 은 물고기 9은 아기상어 위치
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N = int(input())
aquarium = [list(map(int,input().split())) for _ in range(N)]
fishs = []
for x in range(N):
    for y in range(N):
        if aquarium[x][y]:
            if aquarium[x][y] == 9:
                shark_x = x
                shark_y = y
time = 0
shark_size = 2
shark_eat = 0
flag = True
while flag:
    eat_fishs = []
    visited = [[0]*N for _ in range(N)]
    shark = []
    shark.append((shark_x,shark_y,0))
    visited[shark_x][shark_y] = 1
    while shark:
        x,y,distance = shark.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < N and 0<= ny< N:
                if not visited[nx][ny]:
                    if aquarium[nx][ny] > shark_size:
                        continue
                    else:
                        visited[nx][ny] = 1
                        if aquarium[nx][ny] == shark_size or aquarium[nx][ny] == 0:
                            shark.append((nx,ny,distance+1))
                        else:
                            shark.append((nx,ny,distance+1))
                            eat_fishs.append((nx,ny,distance+1))
    if not len(eat_fishs):
        break
    else:
        eat_fishs.sort(key=lambda x: (x[2],x[0],x[1]))
        aquarium[shark_x][shark_y] = 0
        shark_x = eat_fishs[0][0]
        shark_y = eat_fishs[0][1]
        shark_eat += 1
        aquarium[shark_x][shark_y] = 9
        time += eat_fishs[0][2]
        if shark_eat == shark_size:
            shark_size += 1
            shark_eat = 0
print(time)
            
    

 아기상어 문제는 조건들을 정리하는 것이 먼저였다.

1. 상어보다 작거나 같은 크기의 물고기들은 지나갈수 있다.

2. 상어는 자기보다 작은 물고기만 먹는다.

3. 가장 가까운 물고기를 먼저 먹는다.

4. 같은 위치에 존재하면, x축이 작은 것을 1순위, y축이 작은것이 2순위이다.

5. 상어의 크기의 개수만큼의 물고기를 먹으면 상어가 커진다.

이 부분을 정리하고 풀면 쉬웠다.

기본적으로 BFS를 하는대신 상대적인 거리를 측정하기 위한 distance를 넣어주었다.

그래서 상어가 먹을 수 있는 모든 물고기의 위치를 파악해주고, 거리를 측정해주었다.

여기서 시간을 더 줄이고 싶으면, 어차피 BFS이기 때문에 최소거리로 측정이 된다.

그러므로, 최초로 먹을수 있는 물고기와의 거리를 측정하고 그 거리보다 큰 것들이 나오는 순간 BFS를 멈춰도 된다.

하지만 시간제한이 널널한 편이었고, 첫시도였기 때문에, 머리로만 생각하고 넘어갔다.

위와 같이 먹을 수 있는 물고기목록을 구한뒤에는 lambda를 통한 다중정렬을 해서 문제 조건에 맞게 오름차순으로 정리해준다.

그리고 선택된 물고기의 위치를 상어의 위치로 바꿔주고, 상어의 크기와 상어의 먹은 물고기의 수를 비교해줘서 같아지면 상어의 크기를 키워주고 먹은 물고기 수를 초기화 시켜줬다.

이 문제에서 시간이 좀 걸렸던 요인은 움직인 상어의 이전 위치의 좌표를 초기화 안 시켜줘서 생겼다. 그냥 상어의 최초위치만 파악하고 난뒤에는 상어의 위치는 지속적으로 추적이 가능하므로, 그냥 상어의 값을 0으로 바꿔주는게 더 편할수 있을 것 같다.

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

N,M = map(int,input().split())

tomatoarray = [list(map(int,input().split())) for _ in range(M)]

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

익은 토마토를 기준으로 상하좌우로 인접한 토마토들만 익는다. 

1일차의 토마토가 익힌 인접 토마토들이 2일차에 새로운 토마토들을 익히게 된다.

그러므로 1일차의 토마토들은 필요 없어진다.

이런한 점을 이용해, 반복문을 통해 새롭게 익은 토마토들을 찾아내고, 그때 토마토 개수를 늘려준다. 

그리고 난뒤 전체 행렬의 크기와 토마토 개수가 같으면 반복문을 탈출하고,

새롭게 익은 토마토들이 있으면, 더 익힐 가능성이 있으므로, 그 리스트를 복사해서 반복해준다.

하지만 새롭게 익은 토마토들이 없으면, 더이상 익힐 가능성이 없으므로, 반복문을 탈출해서 -1을 출력해주면 된다.

# 7569 토마토

M,N,H = map(int,input().split())

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

tomatoarray =[ [list(map(int,input().split())) for _ in range(N)] for _ in range(H)]
# tomato dz dx dy
# H,N,M

total = N*M*H
tomatocnt = 0
tomatos = []
result = -1
day = 0
for x in range(N):
    for y in range(M):
        for z in range(H):
            if tomatoarray[z][x][y] == 1:
                tomatos.append((x,y,z))
                tomatocnt += 1
            elif tomatoarray[z][x][y] == -1:
                total -= 1
if total == tomatocnt:
    result = 0
else:
    while tomatos:
        new_tomato = []
        for x,y,z in tomatos:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<N and 0<=ny<M and 0<=nz<H:
                    if not tomatoarray[nz][nx][ny]:
                        tomatoarray[nz][nx][ny] = 1
                        tomatocnt += 1
                        new_tomato.append((nx,ny,nz))
        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomatos = [row[:] for row in new_tomato]
        else:
            result = -1
            break
print(result)

이 문제는 7576번 문제의 3D 버전이다 여기서 조심해야할 것은 3차원이고, x,y,z의 순서를 조심해주면 된다.

보통 문제를 풀때 나같은 경우 x축을 행으로 하고 y축을 열로 한다. 자신만의 기준을 가지고, 헷갈리지 않게 조심하면 될 것 같다.

기본 원리는 7576번하고 같다.

# 2178번
# 문제
# N*M 크기의 배열
# (1,1) => (N,M) 까지 가야한다.
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())

maze = [list(input()) for _ in range(N)]


visted = [[0]*M for _ in range(N)]


stack = deque()
stack.append((0,0))
visted[0][0] = 1
flag = False
while not flag:
    x,y = stack.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx == N-1 and ny == M-1:
            flag = True
            visted[nx][ny] = visted[x][y] + 1
            break
        elif 0<=nx<N and 0<=ny<M:
            if not visted[nx][ny] and maze[nx][ny] == '1':
                visted[nx][ny] = visted[x][y] + 1
                stack.append((nx,ny))
print(visted[N-1][M-1])

이 문제는 시작위치와 도착위치가 정해져있고, 최소 이동거리를 찾는것이므로, visited라는 maze와 똑같은 사이즈의 리스트를 만들어두고, 그 안에 이동거리를 저장해주었다. 그리고 도착위치에 도착하면 break를 해주었고, 그때의 flag를 바꿔주어서 상단의 while문도 빠져나갈수 있게 해주었다.

# 1697 숨바꼭질

#  수빈이는 N 동생은 K 
#  수빈이는 X-1 or X+1 2*X


N,M = map(int,input().split())

result = 0
stack = [(N,0)]
visited = [0]*100001
while stack:
    cu_n,cnt = stack.pop(0)
    if cu_n == M:
        break
    if 0<= cu_n <= 100000:
        if 0<= cu_n -1 <= 100000:
            if not visited[cu_n-1]:
                visited[cu_n-1] =1
                stack.append((cu_n-1,cnt+1))
        if 0<= cu_n+1 <= 100000:
            if not visited[cu_n+1]:
                visited[cu_n+1] =1
                stack.append((cu_n+1,cnt+1))
        if 0<= cu_n*2 <= 100000:
            if not visited[cu_n*2]:
                visited[cu_n*2] =1
                stack.append((cu_n*2,cnt+1))
print(cnt)

BFS의 일종으로 볼 수 있다.

 현재 위치에서 +1, -1 , *2 를 했을 때의 값을 추가해주고, BFS에서는 먼저 들리는 곳이 가장 가까운 곳이므로, 한번 방문했던 곳은 연산량을 줄이기 위해 방문을 표시해주었다. 그리고 최초로 목표 위치인 M을 방문하면 반복문을 멈추게 했다.