취업 리부트 코스 4주차(1,2) - 시뮬레이션

알고리즘 마지막 주차가 됐다. 이번 주차에서는 시뮬레이션과 완전 탐색, 그리디와 다익스트라, 다이나믹 프로그래밍이 남았다. 아직 dfs와 같은 알고리즘 기법을 이용한 풀이가 익숙하지 않아서 시뮬레이션 문제가 어렵다 어려워!
멘토님이 백준의 미세먼지를 추천해주셔서 다시 돌아보았다. 1일차때 이해가 제대로 안갔는데 2일차때 계속 다시 풀이를 듣고 써보고 하니 어제보단 이해가 늘었는지 조금 푸는 방식이 눈에 보인다.

유튜브에 검색해보니 문어박사 IT편의점이라는 코딩 문제를 내시는 분이 친절하게 풀이 영상을 올려주셔서 그 코드를 기준으로 학습하였다.

백준 17086: 아기 상어2

# 상어에서부터 검색을 시작(1인곳). 8개의 방향을 탐색, 범위 내인지 확인
from collections import deque

# [0] 입력 받기
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# [1] 8가지 이동방향 설정 -> for문에 이용
d = [(1,0),(-1,0),(0,-1),(0,1),(-1,-1),(1,-1),(-1,1),(1,1)]
q = deque() # 상어의 위치가 담길 곳

# [2] 상어 위치를 받아서 bfs 탐색. 상어가 없는곳은 처음에 0이다.
def bfs():
    while q: #새로운 지점을 큐에 담을거라 사용시 popleft()
        x, y = q.popleft()
        for dx, dy in d:
            # 현재 위치에서 각 이동할 방향들 더함
            nx, ny = x + dx, y + dy
            # 범위 내부인지 확인
            if 0 <= nx < N and 0 <= ny < M:
                # 상어가 없는 곳인지
                if not graph[nx][ny]: # if not -> 0(False) 이라면
                    graph[nx][ny] = graph[x][y] + 1
                    # nx,ny에서 다시 8방향으로 탐색해야함
                    q.append((nx,ny))
                    
# [3] 처음에 사용할 상어 위치 찾기
for i in range(N):
    for j in range(M):
        if graph[i][j]: # 0이 아니면 상어가 있는 곳
            q.append((i,j))

bfs()
ans = map(max, graph)
print(max(ans)-1)

미세먼지에 오래 시간을 써서 그런지 아기 상어2 문제는 아직 혼자 다 풀긴 어렵지만 흐름을 따라갈 수 있었다.

미세먼지 문제는 공기청정기가 퍼지는 방향으로 for문을 수작업 해줘야 했는데 범위 설정이 헷갈린다...
백준 17144: 미세먼지 안녕!

"112012KB	328ms"

import sys
input = sys.stdin.readline

# [0] 입력값 받기
R, C, T = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(R)]

# [1] 청정기 위치 저장
for i in range(R):
    if arr[i][0] == -1:
        i1, i2 = i, i+1
        arr[i1][0] = arr[i2][0] = 0 # 0으로 초기화
        break
        
# T초동안 확산과 정화
for _ in range(T):
    # [2] 먼지 확산 (arr 복사해서 확산하고 대입하기)
    arr_t = [x[:] for x in arr]
    for i in range(R):
        for j in range(C):
            if arr[i][j] > 4: # 5로 나눈 몫이 퍼지기 때문
                t = arr[i][j] // 5 # 4방향으로 퍼질 먼지 양
                for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
                    # 상하좌우 4번
                    ni, nj = i+di, j+dj # 현재 위치에서 한칸씩
                    # 지정된 크기 내에서, 청정기 위치 아니라면
                    if 0<=ni<R and 0<=nj<C and (ni,nj) != (i1,0) and (ni,nj) != (i2,0):
                        arr_t[i][j] -= t
                        arr_t[ni][nj] += t
    arr = arr_t

    # [3] 순환
    # 상단 공기순환
    for i in range(i1 - 1, 0, -1):  # 위쪽으로 이동하는 공기순환
        arr[i][0] = arr[i - 1][0]
    for j in range(C - 1):  # 오른쪽으로 이동하는 공기순환
        arr[0][j] = arr[0][j + 1]
    for i in range(i1):  # 아래쪽으로 이동하는 공기순환
        arr[i][-1] = arr[i + 1][-1]
    for j in range(C - 1, 0, -1):  # 왼쪽으로 이동하는 공기순환
        arr[i1][j] = arr[i1][j - 1]
    arr[i1][1] = 0  # 공기순환 후 공기청정기 옆 미세먼지 0으로 초기화

    # 하단 공기순환
    for i in range(i2 + 1, R - 1):  # 아래쪽으로 이동하는 공기순환
        arr[i][0] = arr[i + 1][0]
    for j in range(C - 1):  # 오른쪽으로 이동하는 공기순환
        arr[-1][j] = arr[-1][j + 1]
    for i in range(R - 1, i2, -1):  # 위쪽으로 이동하는 공기순환
        arr[i][-1] = arr[i - 1][-1]
    for j in range(C - 1, 0, -1):  # 왼쪽으로 이동하는 공기순환
        arr[i2][j] = arr[i2][j - 1]
    arr[i2][1] = 0  # 공기순환 후 공기청정기 옆 미세먼지 0으로 초기화

# map(sum(arr)) -> 각 행의 합계
ans = sum(map(sum, arr))
print(ans)

프로그래머스: 카카오 크레인 인형뽑기 게임

미세먼지의 단련되었는지 이 문제는 해설이 친절하기도 해서 풀기가 너무 편했다! 먼저 어떻게 풀건지 작성해보고 코드로 접근했는데 잘 풀려나갔다. 어려운 문제는 아니었지만 수월하게 풀어서 기분이 좋았던 문제...