[백준 21922번] 파이썬 - 학부 연구생 민상

백준 21922 - 학부 연구생 민상

시간 제한 1초, 메모리 제한 512MB

# 조건

• 학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.
• 연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4$4$방향으로 분다.
  • 물론 에어컨이 위치한 곳에도 바람이 분다.
• 민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.
• 연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.
• 연구실에 있는 물건의 종류는 총 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$개 이하가 들어온다.

출력

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

# 접근 방법

• 입력받은 연구실을 탐색하며 에어컨이 있는 위치를 리스트에 담아주고 bfs를 시작한다.
• 벽의 종류에 따라 방향이 달라지므로 방향이 달라지는 경우를 생각해주어야 한다.
  • 1번과 2번 벽의 경우 따로 정의하지 않고 bfs를 돌리며 조건을 걸어준다
  • 1번의 경우 좌우에서 오다가 만나면 continue
  • 2번의 경우 위아래로 오다가 만나면 continue => 왔던 길을 돌아가기 때문에
  • 3번은 아래 => 왼쪽, 위 => 오른쪽
    • 즉, 1, 0 에서 0, -1 과 -1, 0에서 0, 1로 변하므로
    • dx, dy = -dy, -dx로 변경하면 된다.
  • 4번의 경우 아래 => 오른쪽, 위 => 왼쪽
    • 따라서 dx, dy = dy, dx로 변경하면 된다.
• 중요한 점은, for 문을 통하여 에어컨 시작 지점에서 4방향 탐색을 돌리고, 한 방향에 대해서는 while문을 이용하여 이동해준다는 점이다.
  • 이 때 바람이 범위를 벗어나거나 다른 에어컨을 만나는 경우 종료해준다.
• 처음엔 무한 루프에 빠지지 않을까라는 생각 때문에 종료 조건에 대한 고민이 있었지만,
  • 무한루프에 빠지기 위해서는 중간에 에어컨을 만나거나, 에어컨에서 나온 바람이 방향 전환하게 되는 벽을 만나기 때문에 따로 종료 조건을 주지 않아도 괜찮다는 것을 알게 되었다!

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

def bfs(ci, cj):  
    q = deque()  
    q.append((ci, cj))  
    while q:  
        si, sj = q.popleft()  

        # 에어컨에 대해서 4방향 탐색하며  
        # 한 방향에 대해서는 while문을 통해 이동        
        for d in range(4):  
            # 방향 전환 위하여 현재 이동 방향 따로 기록해주기  
            dx, dy = di[d], dj[d]  
            ni, nj = si + dx, sj + dy  
            while 0<=ni<N and 0<=nj<M:  
                visited[ni][nj] = 1  
                # 에어컨 만나면 종료 -> 중복 방문하기 때문에  
                if arr[ni][nj] == 9:  
                    break  
                # 벽은 만나는 경우 체크해주어야 하는데  
                # 3번 벽은 -> 아래로 가면 왼쪽으로 전환, 왼쪽으로 가면 아래로 전환                
                #             즉, 1, 0 에서 -1, 0으로 -1, 0에서 0, 1로 변경                
                #             => dx, dy = -dy, -dx로 변경해주면 된다.                
                # 4번 벽은 -> 아래로 가면 오른쪽, 오른쪽으로 가면 아래로 전환                
                #              1, 0에서 0, 1로 0,1에서 1,0이므로           
                #              => dx, dy = dy, dx                
                # 1번 벽의 경우 왼쪽 오른쪽 이동 중 1번 벽을 만나면 왔던 길을 돌아가므로 종료,                
                # 2번도 위아래 이동 중 만나면 종료                
                if arr[ni][nj] == 3:  
                    dx, dy = -dy, -dx  
                elif arr[ni][nj] == 4:  
                    dx, dy = dy, dx  
                elif arr[ni][nj] == 1 and dx == 0:  
                    break  
                elif arr[ni][nj] == 2 and dy == 0:  
                    break  

                ni += dx  
                nj += dy  

N, M = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
air_conditional = []  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 9:  
            air_conditional.append((i, j))  

di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
visited = [[0] * M for _ in range(N)]  
for i, j in air_conditional:  
    visited[i][j] = 1  
    bfs(i, j)  

result = 0  
for i in visited:  
    result += i.count(1)  
print(result)