Crush on Study

나머진 다 쉬웠는데, 가장 가까운 경로에 있는 애를 어떻게 먹으러갈지 구현하기 힘들었던 문제.

우선순위가

1. 자기보다 크기가 작은 물고기가 2마리 이상인 경우 가장 가까이에 있는 것

2. 거리가 같은 경우에는 행과 열이 작을 수록.

이건데 1번을 건너뛰고 자꾸 2번 우선순위로 가가지고 힘들었음.

다른 골3에 비해 얘가 좀 더 어려웠던 느낌

import sys
from collections import deque
sys.stdin = open('111.txt')

input = sys.stdin.readline

N = int(input().rstrip())
graph = []
for col in range(N):
    graph.append(list(map(int,input().rstrip().split())))
    for row in range(N):
        if graph[col][row] == 9:
            sy,sx = col,row # 상어 위치 저장
            graph[col][row] = 0
    

q = deque()


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

# 물고기 찾으러 감
def search():
    visited = [[-1]*N for _ in range(N)]
    visited[sy][sx] = 0 # 상어 시작 위치
    q.append((sy,sx))
    
    while q:
        y,x = q.popleft()
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<=ny<N and 0<=nx<N:
                if visited[ny][nx] == -1:
                    if -1<=graph[ny][nx] <= shark_size:
                        visited[ny][nx] = visited[y][x]+1
                        q.append((ny,nx))
                        
    return visited


def eating(visited):
    min_check = int(1e9)
    for col in range(N):
        for row in range(N):
            if 1<=graph[col][row] < shark_size:
                if visited[col][row] != -1:
                    if visited[col][row] < min_check:
                        min_check = visited[col][row]
                        sy,sx = col,row
                        
    if min_check == int(1e9):
        return False # 더 이상 먹을게 없다는 뜻
    
    return sy,sx,min_check

time = 0
eat_cnt = 0 # 물고기 먹은 횟수
while True:
    visited = search()    
    result = eating(visited)
    
    if result == False:
        print(time)
        break
    
    sy,sx = result[0],result[1] # 상어 재 시작 위치
    time += result[2]
    graph[sy][sx] = 0
    eat_cnt += 1
    
    if eat_cnt >= shark_size:
        shark_size+=1
        eat_cnt = 0

회전하는 방식에서 상당히 애를 먹음. 이 부분만 잘 처리하면 나머진 기본적인 플러드필이다.

# N은 격자 사이즈, Q는 레벨 횟수
import copy
from collections import deque
N,Q = map(int,input().split())

_N = 2**N # 제곱 수라했으니까.

ice = []
for col in range(_N):
    ice.append(list(map(int,input().split())))

level = list(map(int,input().split()))

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

### 위에 입력 이상 없음 ###
for idx in level:
    k = 2**idx # 레벨 단위로 해야하니까
    for col in range(0,_N,k):
        for row in range(0,_N,k):
            temp = []
            for small_col in range(col,col+k):
                temp.append(ice[small_col][row:row+k])

            for small_col in range(k):
                for small_row in range(k):
                    # 시계방향 회전
                    ice[col+small_row][row+k-small_col-1] = temp[small_col][small_row]

    
    ice_check = [[0]*_N for _ in range(_N)]
    for col in range(_N):
        for row in range(_N):
            cnt = 0
            for i in range(4):
                ny = col+dy[i]
                nx = row+dx[i]
                if 0<=ny<_N and 0<=nx<_N and ice[ny][nx]>0:
                    cnt +=1

            ice_check[col][row] = cnt

    for col in range(_N):
        for row in range(_N):
            if ice_check[col][row] < 3: # 인접 얼음이 3개 미만이면
                if ice[col][row] > 0: # 그리고 그 중심에 얼음이 있다면
                    ice[col][row] -= 1


### 위에꺼 다 끝내고 나면!
def bfs(y,x):
    global ccnt
    q = deque()
    q.append((y,x))

    while q:
        y,x = q.popleft()
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<=ny<_N and 0<=nx<_N:
                if not visited[ny][nx] and ice[ny][nx] > 0:
                    visited[ny][nx] = True
                    ccnt+=1
                    q.append((ny,nx))

    return ccnt


arr = []
visited = [[False]*_N for _ in range(_N)]
ccnt = 0
for col in range(_N):
    for row in range(_N):
        if ice[col][row] > 0 and not visited[col][row]:
            visited[col][row] = True
            ccnt = 1
            result = bfs(col,row)
            arr.append(result)

tot = 0
for col in range(_N):
    for row in range(_N):
        tot += ice[col][row]

if tot!=0:
    print(tot)
    print(max(arr))
    
else:
    print(tot)
    print(0)

하라는 대로만 하면 되는 문제다. 시간이 빡빡해보였는데 한번에 통과해서 기분 좋다.

이 문제에서는 주의해야할 점은..... 죽은 나무를 언제 처리할 것인지 생각하는게 관건이다.

clear와 extend 함수 스킬을 알고 있어서 다행이었다.

# N은 격자 사이즈, M은 바이러스 개수, K는 사이클 횟수
N,M,K = map(int,input().split())

# 초기 배양액
init_eat = [[5]*N for _ in range(N)]

# 사이클 1회 마치고 추가될 양분
add_eat = []
for col in range(N):
    add_eat.append(list(map(int,input().split())))

# 바이러스 정보들
virus = [[[] for _ in range(N)] for _ in range(N)]
for col in range(M):
    y,x,age = map(int,input().split())
    virus[y-1][x-1].append(age)

# 방향 키
step = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)]

#### 입력 이상 X ####

# 1번/2번 행동 시작
def eating():
    for col in range(N):
        for row in range(N):
            if virus[col][row]: # 바이러스가 있는 곳이라면
                virus[col][row].sort() # 나이가 어린 바이러스부터 먹어야하므로,
                temp = []
                dead = 0
                for age in virus[col][row]:
                    if age <= init_eat[col][row]: # 양분이 나이보다 크거나 같을 경우
                        init_eat[col][row] -= age
                        age+=1
                        temp.append(age)

                    else:
                        dead += age//2 # 현재 나이의 절반만큼의 양분

                init_eat[col][row] += dead
                virus[col][row].clear() # 한번 싹 치워주고
                virus[col][row].extend(temp)


# 3번 행동 시작
def grow():
    for col in range(N):
        for row in range(N):
            if virus[col][row]: # 바이러스가 있다면
                for age in virus[col][row]:
                    if age%5==0:
                        for idx in step:
                            ny = col+idx[0]
                            nx = row+idx[1]
                            if 0<=ny<N and 0<=nx<N:
                                virus[ny][nx].append(1) # 나이가 1인 나무 추가

for _ in range(K):
    eating()
    grow()
    for col in range(N):
        for row in range(N):
            init_eat[col][row] += add_eat[col][row]

tot = 0
for col in range(N):
    for row in range(N):
        if virus[col][row]:
            tot += len(virus[col][row])

print(tot)

https://www.acmicpc.net/problem/15686

백트랙킹을 사용하는 문제입니다.

import sys
sys.setrecursionlimit(10**8)
sys.stdin = open('111.txt')

N,M = map(int,input().split()) # N은 격자 사이즈, M은 치킨집 개수
graph = []
house = []
chicken = []


for col in range(N):
    graph.append(list(map(int,input().split())))
    for row in range(N):
        if graph[col][row] == 1:
            house.append((col,row))
            
        elif graph[col][row] == 2:
            chicken.append((col,row))

기본적으로 먼저 짜둬야 하는 코드들입니다.

그래프 정보를 받을 때, 집과 치킨집의 좌표를 따로 받아줍니다.

이제 백트랙킹을 이용해서 각 집마다 치킨집과의 거리를 다 구해볼게요.

2차원에서 각 좌표들끼리의 조합을 구하는 방법은 거의 공식처럼 쓰입니다.

혹시, 이 문제를 풀기 전에 백준에서 N과M 시리즈를 푸셨다면 1차원에서 조합을 짜는 법은

손에 익으셨을텐데요. 2차원에선 막막할겁니다.

안그렇다구요? 재능러시군요.

저는 일단 이 문제를 처음 봤을 때, combinations을 쓰면 풀 수는 있지만 재귀를 사용해서 풀고자 했습니다. 근데 아이디어가 안 떠올라서 모 블로그를 참고해서 구현하는 방법을 참고했어요. 알고보니 공식처럼 쓰이더라구요.

2차원에서 좌표를 조합하는 방법부터 먼저 짚고 가겠습니다. 금방합니다!

arr = []
def back(num,cnt):
    if num>len(chicken):
        return
    
    if cnt==M:
        for idx in arr:
            cx,cy = chicken[idx]
            print((cx,cy),end=" ")
        return

    arr.append(num)
    back(num+1,cnt+1)
    arr.pop()
    back(num+1,cnt)

(back(0,0))

자, 이게 공식처럼 쓰이는 2차원 백트랙킹 조합 코드입니다.

아래 테케를 기준으로 위 백트랙킹 코드로 치킨집 좌표들을 뽑아보면요.

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

구분이 잘 안가있지만

(0,1) , (3,0)

(0,1) , (4,0)

(0,1) , (4,1)

.

.

.

이런 식으로 좌표가 스윽 나옵니다.

여기서 num > len(chicken)의 역할은 치킨 리스트에 담은 좌표들의 개수보다 넘어가면 인덱스에러가 뜨기때문에, 그걸 잡아주는 역할을 합니다. cnt는 최대 몇개의 좌표를 뽑을지 보는 것이라 cnt==M이 되면 이제 좌표 쌍을 뽑도록 합니다.

위 코드는 그냥 공식처럼 받아들이시면 됩니다.

그렇게 치킨 좌표들 다 뽑았으면 이제 집이랑 같이 이중 포문 돌려서 각각의 거리들을의 모든 합을 다 구해주면 됩니다.

그걸 min함수를 이용해서 계속 갱신해주면 되겠습니다.

아래는 해답코드이며 복붙해가실 때는 sys.stdin = open 이부분 주석처리해주세요~

import sys
sys.setrecursionlimit(10**8)
sys.stdin = open('111.txt')

N,M = map(int,input().split()) # N은 격자 사이즈, M은 치킨집 개수
graph = []
house = []
chicken = []


for col in range(N):
    graph.append(list(map(int,input().split())))
    for row in range(N):
        if graph[col][row] == 1:
            house.append((col,row))
            
        elif graph[col][row] == 2:
            chicken.append((col,row))


arr = []
real_check = int(1e9)
def back(num,cnt):
    global real_check
    if num>len(chicken):
        return
    
    if cnt==M:
        result_tot = 0
        for hx,hy in house:
            min_check = int(1e9)
            for idx in arr:
                cx,cy = chicken[idx]
                min_check = min(min_check,abs(hx-cx)+abs(hy-cy))
                
            result_tot+=min_check
            
        real_check = min(result_tot,real_check)
        return

    arr.append(num)
    back(num+1,cnt+1)
    arr.pop()
    back(num+1,cnt)
    return real_check

print(back(0,0))