백준 21922(학부 연구생 민상) - 해결(pypy)

학부 연구생 민상

 

문제

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 $4$방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

물건 종류	물건 모양	바람의 이동 방향
물건 1
물건 2
물건 3
물건 4

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

 

입력

첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다.

두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다.

 $1,2,3,4$는 위에서 설명한 물건의 종류이다.

 $9$는 에어컨을 의미하고, $0$은 빈 공간을 의미한다.

에어컨은 $0$개 이상 $50$개 이하가 들어온다.

 

출력

민상이가 원하는 자리의 개수를 출력한다.

---

예제 입력 1 복사

8 8
0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 4
0 1 0 0 3 0 0 3
0 0 0 0 0 0 1 0
0 1 0 9 0 0 4 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0

예제 출력 1 복사

25

맨 왼쪽 맨 위를 $(1, 1)$이라 했을때 에어컨이 있는 위치는 $(5, 4)$에 있다. 

이 에어컨에서 나오는 바람의 이동과 민상이가 앉을 수 있는 자리를 표시한 그림이다.

---

구현 문제라서 알고리즘 적으로 생각을 해보았다.

일단 에어컨를 찾고 선풍기에서 4방향으로 바람이 나갈 때 이동방향이 어떻게 달라 지나를 생각해보았다.

처음에는 visit 를 결과를 위해서만 사용하였다. 방향을 사용해서 visit 를 확인해보려고 하였지만 결과는 더 느렸다.

그리고 물건을 만났을 때 방향만 전환해주면서 dfs 방식으로 탐색하였다. dfs 에는 위치와 방향을 넣었다.

하지만 python 으로 61퍼 쯤에서 시간초과가 발생하여 pypy로 풀었다.

import sys
input = sys.stdin.readline

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

# 맵을 저장하면서 
# 에어컨의 위치를 저장
maps = []
list_9 = []
for i in range(N):
    input_list = list(map(int,input().split()))
    for j in range(len(input_list)):
        if input_list[j] == 9:           
            x, y = i, j
            list_9.append((x,y))
    maps.append(input_list)

# 방문한 곳을 저장(결과 출력용) 
visit = [[0] * M for _ in range(N)]
# 방향
dirs = [(-1,0),(0,1),(1,0),(0,-1)]

# dfs 하기 위한 q
q = []
# 일단 에어컨의 4방향을 담는다.
for x, y in list_9:
    visit[x][y] = 1
    q.extend([(x,y,0),(x,y,1),(x,y,2),(x,y,3)])
# 탐색
while q:
    now_x, now_y, now_dir = q.pop()
    # 다음 위치
    next_x, next_y = now_x + dirs[now_dir][0], now_y + dirs[now_dir][1]
    # 범위 안인지 확인
    if 0 <= next_x < N and 0 <= next_y < M:
        # 각 칸을 확인 
        # 0이면 같은 방향으로 지나가기
        if maps[next_x][next_y] == 0:
            q.append((next_x,next_y,now_dir))
        # 1이면 오른쪽(1), 왼쪽(3)만 막히고 다른 방향은 일정
        elif maps[next_x][next_y] == 1:
            if now_dir == 1 or now_dir == 3:
                pass
            else:
                next_dir = now_dir
                q.append((next_x,next_y,next_dir))
        # 2이면 위쪽(0), 아래쪽(2)만 막히고 다른 방향은 일정
        elif maps[next_x][next_y] == 2:
            if now_dir == 0 or now_dir == 2:
                pass
            else:
                next_dir = now_dir
                q.append((next_x,next_y,next_dir))
        # 3이면 위(0)는 오른쪽(1)으로 오른쪽은 위로/ 왼쪽(3)은 아래(2)로 아래는 왼쪽으로 방향이 바뀐다.
        elif maps[next_x][next_y] == 3:
            if now_dir == 0 or now_dir == 1:
                next_dir = 1 - now_dir
            else:
                next_dir = 5 - now_dir
            q.append((next_x,next_y,next_dir))
        # 4이면 위(0)는 왼쪽(3)으로 왼쪽은 위로/ 아래쪽(2)은 오른쪽(1)으로 오른쪽은 아래쪽으로 방향이 바뀐다.
        elif maps[next_x][next_y] == 4:
            next_dir = 3 - now_dir
            q.append((next_x,next_y,next_dir))
        visit[next_x][next_y] = 1

# 총 방문한 곳을 계산
result = 0
for vi in visit:
    result += sum(vi)
print(result)