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

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())

arr = []
aircon = deque()
visited = [[[True for _ in range(4)] for _ in range(M)] for _ in range(N)]
total_set = set()
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(M):
        if temp[y] == 9:
            aircon.append((x,y,[0,1,2,3]))
            temp[y] = 0
            total_set.add((x,y))
            for i in range(4):
                visited[x][y][i] = False

    arr.append(temp)


if aircon:
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    rotate_dict = {
        1 : [0,-1,2,-1],
        2 : [-1,1,-1,3],
        3 : [3,2,1,0],
        4 : [1,0,3,2]
    }
    # 북,서,남,동
    while aircon:
        x,y,dire = aircon.pop()
        for i in dire:
            nx = x + dx[i]
            ny = y + dy[i]
            while 0<=nx<N and 0<=ny<M and visited[nx][ny][i] and visited[nx][ny][(i+2)%4] and not arr[nx][ny]:
                visited[nx][ny][i] = False
                visited[nx][ny][(i+2)%4] = False
                total_set.add((nx,ny))
                nx = nx + dx[i]
                ny = ny + dy[i]
            if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
                if rotate_dict[arr[nx][ny]][i] != -1:
                    visited[nx][ny][i] = False
                    visited[nx][ny][(i+2)%4] = False
                    visited[nx][ny][rotate_dict[arr[nx][ny]][i]] = False
                    total_set.add((nx,ny))
                    aircon.append((nx,ny,[rotate_dict[arr[nx][ny]][i]]))
                else:
                    visited[nx][ny][i] = False
                    visited[nx][ny][(i+2)%4] = False
                    total_set.add((nx,ny))
    print(len(total_set))
else:
    print(0)

 

 

tony9402님이 1회차 문제들 중에 푸는데 가장 오래걸렸던 문제였다.

 

처음에 아슬아슬하게 통과했는데, 이 코드 같은경우엔 통과가 될수도 안될수도 있을정도의 커트라인에 걸친 코드이다.

 

이 첫 풀이의 아이디어는 다음과 같다. N*M*4의 visitied를 만들어놔서, 방문표시를 해주었다.

 

그리고 방문표시를 할때, 서로 반대되는 경우와 회전을 했을때에는, 반대되는 경우 + 회전하는경우까지 전부 방문 처리를 해주었다.

 

위와 같은 작업을 하고, BFS를 돌리면서 전체 방문을 한 위치들을 set에 넣어서 길이를 출력해주었다.

 

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
def func(row):
    return row.count(True)
arr = []
aircon = deque()
visited = [[False for _ in range(M)] for _ in range(N)]
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(M):
        if temp[y] == 9:
            aircon.append((x,y,[0,1,2,3]))
            visited[x][y] = True

    arr.append(temp)


if aircon:
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    rotate_dict = {
        1 : [0,-1,2,-1],
        2 : [-1,1,-1,3],
        3 : [3,2,1,0],
        4 : [1,0,3,2]
    }
    # 북,서,남,동
    while aircon:
        x,y,dire = aircon.pop()
        for i in dire:
            nx = x + dx[i]
            ny = y + dy[i]
            while 0<=nx<N and 0<=ny<M :
                if arr[nx][ny] == 9:
                    break
                visited[nx][ny] = True
                if 0<=nx<N and 0<=ny<M and arr[nx][ny]:
                    if rotate_dict[arr[nx][ny]][i] != -1:
                        i = rotate_dict[arr[nx][ny]][i]
                    else:
                        break
                nx = nx + dx[i]
                ny = ny + dy[i]

    b = sum(list(map(func,visited)))
    print(b)
else:
    print(0)

 깔끔한 풀이는 다음과 같다.

 

이 풀이는 다음과 같다. 에어컨 바람은 언제 멈추면될것인가 이다.

 

 

문제를 읽어보면 에어컨 바람이 멈출 만한 곳은 총 3가지 경우이다.

 

1. 연구실 범위를 벗어났을때

 - 당연하게 연구실 밖으로 바람이 벗어나면 돌아올 방법이 없으므로, 연구실 범위가 벗어났을때, 에어컨 바람은 그만둔다.

 

2. 다른 에어컨을 만났을때

 - 다른 에어컨을 만났을때 왜 멈춰야하는지 의문을 표할수도 있다. 하지만 생각을 해보면, 우리는 어떠한 경로를 통해 

   A에어컨에서 B에어컨까지 왔다. 그러면 B에어컨에서도 똑같이 A에어컨으로 갈 수 있는 경로가 생긴 것이다.

 

  각 에어컨은 상하좌우로 전부 돌기 때문에, 가능한 것이다. 그러므로 다른 에어컨에 만났을 때, 거기서부터의 바람의 이동은 그 에어컨에서 다시 탐색을 하면 되는 것이다.

 

3. 물건1,2의 방향과 수직되는 방향의 바람이 들어왔을 때

 - 이때는 경우2번을 생각해보면 똑같다. 우리는 특정한 경로를 통해 물건1, 2로 왔을 것이다. 그런데 수직되는 방향으로 바람이 들어오면, 그 바람은 반대로 되돌아 간다. 즉, 우리가 왔던 길로 되돌아가서, 우리가 최초로 바람이 왔던 에어컨으로 돌아간다.

  그러면, 그때의 반대방향으로 가는 바람은 우리가 상하좌우를 전부 탐색을 할 것이기때문에, 이미 탐색범위에 있다.

 그렇기 때문에 굳이 다시 탐색을 할 필요가 없다.

 

 

그러므로 위의 3가지경우를 제외하고는 방향을 계속 전환을 해주면서 방문표시를 해주면된다.

 

이 방문 표시는 재방문을 방지하기 위한 방문표시가 아니라, 에어컨의 바람이 어디까지 영향을 줬는지 세기 위한 것이다.

 

 

그래서 나는 3가지 경우를 제외하고는 계속해서 돌도록 while문을 돌려주었고,

 

전부 돌리고 난뒤에 visited의 True의 개수를 세어, 출력을 해주었다.

 

 

낮은 난이도의 문제였지만, 처음 잘못잡은 아이디어와 접근방법으로 인해 가장 오래걸리고 고생했던 문제였다.