[백준 - 21922] 학부 연구생 민상

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

 

 

 - 9: 에어컨

 - 0: 빈자리

 - 물건 1: 세로로만 통과 

 - 물건 2: 가로로만 통과

 - 물건 3: /(사각형의 대각선) 북동남서 -> 동북서남

 - 물건 4: \(사각형의 다른 대각선) 북동남서 -> 서남동북

 

구현 코드

import sys
from collections import deque

# 사방으로 뻗어나가지만 진행되는 탐색에는 방향이 부여되어있다.
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def chge_dir(tile, cd):
    nd = -1
    if tile == 1:
        if cd in (1, 3):
            return -1
        else:
            return cd
    elif tile == 2:
        if cd in (0, 2):
            return -1
        else:
            return cd
    elif tile == 3:
        if cd == 0:
            nd = 1
        elif cd == 1:
            nd = 0
        elif cd == 2:
            nd = 3
        elif cd == 3:
            nd = 2
        return nd
    elif tile == 4:
        if cd == 0:
            nd = 3
        elif cd == 1:
            nd = 2
        elif cd == 2:
            nd = 1
        elif cd == 3:
            nd = 0
        return nd
    else:
        return cd

def main():
    ret = 0
    visit = [[[0]*4 for _ in range(M)] for _ in range(N)]
    
    def bfs(x, y):
        q = deque([(x+d[i][0], y+d[i][1], i) for i in range(4) if x+d[i][0] >= 0 and x+d[i][0] < N and y+d[i][1] >= 0 and y+d[i][1] < M and grid[x+d[i][0]][y+d[i][1]] != 9])
        for i in range(4):
            if x+d[i][0] >= 0 and x+d[i][0] < N and y+d[i][1] >= 0 and y+d[i][1] < M:
                if not visit[x+d[i][0]][y+d[i][1]][i] and grid[x+d[i][0]][y+d[i][1]] != 9:
                    visit[x+d[i][0]][y+d[i][1]][i] = 1 
        
        while q:
            cx, cy, cd = q.popleft()

            nd = chge_dir(grid[cx][cy], cd)
            if nd == -1:
                continue

            nx, ny = cx + d[nd][0], cy + d[nd][1]

            # 격자 바깥 제외
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
                
            if not visit[nx][ny][nd] and grid[nx][ny] != 9:
                visit[nx][ny][nd] = 1
                q.append((nx, ny, nd))

        return           
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 9:
                for k in range(4):
                    visit[i][j][k] = 1
                bfs(i, j)

    for i in range(N):
        for j in range(M):
            for k in range(4):
                if visit[i][j][k]:
                    ret += 1
                    break
    return ret

if __name__ == "__main__":
    input = sys.stdin.readline
    N, M = tuple(map(int, input().split()))
    grid = [list(map(int, input().split())) for _ in range(N)]
    print(main())

TL; DR

• 에어컨이 접해있는 케이스
• 바람이 순환할때 무한루프 돌수 있다.
• pypy로 제출