| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.
연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.
민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.
연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.
연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.
연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.
민상이가 원하는 자리는 몇 개 있는지 계산해주자.
입력
첫 번째 줄에는 연구실의 크기가 세로 N(1 ≤ N ≤ 2,000), 가로 M(1 ≤ M ≤ 2,000) 순으로 주어진다.
두 번째 줄부터 N + 1 줄까지 연구실 내부 구조 정보를 알려주는 값 M개가 주어진다.
1, 2, 3, 4는 위에서 설명한 물건의 종류이다.
9는 에어컨을 의미하고, 0은 빈 공간을 의미한다.
에어컨은 0개 이상 50개 이하가 들어온다.
출력
민상이가 원하는 자리의 개수를 출력한다.
풀이
최대 4,000,000칸을 최대 50회 탐색해야 한다면 2억 번의 연산으로 시간 제한 내에 문제를 해결하기 어렵다. 따라서 탐색을 일부 생략할 방법을 고민해봐야 하는데, 연구소의 한 자리에 같은 방향으로 부는 바람에 대한 탐색은 시도하지 않아도 된다. 어차피 같은 방향의 바람이 이전에 탐색을 끝냈다면 앞으로 바람의 진행방향은 이전의 탐색과 완전히 같을 것이기 때문이다. 따라서 각 자리마다 탐색 여부를 방향과 함께 저장해야 한다. 여기서 바람의 방향을 비트로 저장해 각 자리가 최대 15까지 탐색 값을 갖도록 했다. 0001은 위쪽, 0010은 오른쪽, 0100은 아래쪽, 1000은 왼쪽으로 예를 들어 오른쪽과 아래쪽 방향으로 탐색했던 칸이라면 0110으로 6이 저장되어있을 것이다. 이 자리에 오른쪽으로 부는 바람이 온다면 AND 연산으로 탐색을 멈출 수 있다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(N)]
wind = [[0] * M for _ in range(N)]
d = [0, (-1, 0), (0, 1), 0, (1, 0), 0, 0, 0, (0, -1)]
for i in range(N):
for j in range(M):
if lab[i][j] == 9:
for k in range(4):
x, y = i, j
t = 1 << k
while 0 <= x < N and 0 <= y < M and wind[x][y] & t == 0:
wind[x][y] |= t
if lab[x][y] == 1:
if t == 2: t = 8
elif t == 8: t = 2
elif lab[x][y] == 2:
if t == 1: t = 4
elif t == 4: t = 1
elif lab[x][y] == 3:
if t == 1: t = 2
elif t == 2: t = 1
elif t == 4: t = 8
else: t = 4
elif lab[x][y] == 4:
if t == 1: t = 8
elif t == 2: t = 4
elif t == 4: t = 2
else: t = 1
x += d[t][0]
y += d[t][1]
seat = 0
for i in range(N):
for j in range(M):
if wind[i][j]:
seat += 1
print(seat)
solution()
