[백준] 21922번: 학부 연구생 민상 Python

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

21922번: 학부 연구생 민상

그래프에서의 시뮬레이션 / 구현 문제이다 

물건 종류 1 ~4 가 있고 해당 물건을 만날때마다 에어컨 바람에 대해서 조치를 취해주어야 한다 (방향을 바꾸거나, 에어컨 바람이 그냥 통과하거나, 더이상 앞으로 가지 않는 경우 3가지가 있다)

처음에 놓친부분은 :

1) 물건 3과 물건 4를 처음에 단순히 시계방향 반시계방향으로 생각했는데 그림을 잘 . 보. 고 해당하는 바람 방향을 어떤 방향으로 바꾸어주는지 일일이 구현해야 한다.. 이걸로 살짝 삽질을 했당

2) 에어컨은 여러개 있을 수 있다 

3) 예제 1번을 보면 알겠지만, 방문한 곳을 다시 방문할 수 있다 !!!!!!!!! 

이 두가지 이다 시뮬레이션 하는건 여러가지 방법이 있겠지만 나는 queue 자료구조를 이용해서 bfs스럽게 풀었다 

그리고 2차원 배열 visited 에 에어컨 바람의 경로를 1로 저장했고, 민상이가 원하는 자리가 결국이 1 로 표시된 공간들이니까 1들을 더해주는 방식으로 답을 구했다. 

from collections import deque 
# 에어컨은 여러개 있을 수 있음 !! 
n, m = map(int, input().split())
array = []
start = []
for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)
    for j in range(m):
        if data[j] == 9:
            start.append((i, j))  # start point
# ↑ → ↓ ←
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def check(i, j):
    if 0 <= i < n and 0<= j < m:
        return True 
    else:
        return False 

# (시계방향) ↑ → ↓ ←
visited = [[0] * m for _ in range(n)]
# ← ↓ → ↑
block_3 = [1,0,3,2]
block_4 = [3,2,1,0]
def simulate():
    queue = deque([])

    for sx, sy in start:
        visited[sx][sy] = 1
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if check(nx, ny):
                queue.append((nx, ny, i)) # i 는 방향 
    
    while queue:
        x, y, dir = queue.popleft()
        visited[x][y] = 1

        if array[x][y] == 0:
            nx = x + dx[dir]
            ny = y + dy[dir]
            if check(nx, ny):
                queue.append((nx, ny, dir))
        elif array[x][y] == 1:
            if dir %2 == 0: # 상, 하 만 통과 가능 
                nx = x + dx[dir]
                ny = y + dy[dir]
                if check(nx, ny):
                    queue.append((nx, ny, dir))
        elif array[x][y] == 2:
            if dir%2 == 1: # 좌, 우 만 통과 가능 
                nx = x + dx[dir]
                ny = y + dy[dir]
                if check(nx, ny):
                    queue.append((nx, ny, dir))
        elif array[x][y] == 3:
            dir = block_3[dir]
            nx = x + dx[dir]
            ny = y + dy[dir]
            if check(nx, ny):
                queue.append((nx, ny, dir))
        elif array[x][y] == 4:
            dir = block_4[dir]
            nx = x + dx[dir]
            ny = y + dy[dir]
            if check(nx, ny):
                queue.append((nx, ny, dir))
            

simulate()
# visited 그래프에서 1의 개수 세어주기 
answer = 0 

for i in range(n):
    answer += sum(visited[i])

print(answer)