[파이썬] 백준 21922: 학부 연구생 민상 (골드5)

21922번: 학부 연구생 민상

첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$

www.acmicpc.net

문제

풀이

0. 방향성 생각

큐에 좌표, 진행방향을 넣고 BFS 돌려준다

만나는 구조물마다 방문처리, 방향처리 해주기.

visit은 특정 좌표에서 상하좌우 4방향을 정의하고 한 방향이라도 에어컨이 들어오면 any를 써서 카운트 해주기.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

aircons = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 9:
            aircons.append((j,i))

q = deque()
step = [(1,0),(-1,0),(0,1),(0,-1)]
visit = [[[False]*4 for _ in range(w)] for _ in range(h)]

for x,y in aircons:
    visit[y][x] = [True]*4
    for i in range(4):
        q.append((x,y,i))

입력 받고, 에어컨 위치 찾기.

visit 4방향으로 정의하기.

에어컨 좌표 visit 4방향 모두 켜주고, 큐에 추가하기.

2. BFS

while q:
    x,y,dire = q.popleft()
    
    for i in range(4):
        if i == dire:
            dx,dy = step[i]
            nx = x + dx
            ny = y + dy

            if 0<=nx<w and 0<=ny<h and not visit[ny][nx][i]:
                if arr[ny][nx] == 0:
                    visit[ny][nx][i] = True
                    q.appendleft((nx,ny,dire))
                
                if arr[ny][nx] == 1:
                    if dire == 1 or dire == 0:
                        visit[ny][nx][0] = True
                        visit[ny][nx][1] = True
                    else:
                        visit[ny][nx][2] = True
                        visit[ny][nx][3] = True
                        q.appendleft((nx,ny,dire))
                
                if arr[ny][nx] == 2:
                    if dire == 2 or dire == 3:
                        visit[ny][nx][2] = True
                        visit[ny][nx][3] = True
                    else:
                        visit[ny][nx][0] = True
                        visit[ny][nx][1] = True
                        q.appendleft((nx,ny,dire))
                        
                if arr[ny][nx] == 3:
                    if dire == 0 or dire == 2:
                        visit[ny][nx][0] = True
                        visit[ny][nx][2] = True
                        if dire==0:
                            q.appendleft((nx,ny,3))
                        else:
                            q.appendleft((nx,ny,1))
                            
                    elif dire == 1 or dire == 3:
                        visit[ny][nx][1] = True
                        visit[ny][nx][3] = True
                        if dire==1:
                            q.appendleft((nx,ny,2))
                        else:
                            q.appendleft((nx,ny,0))
                            
                if arr[ny][nx] == 4:
                    if dire == 0 or dire == 3:
                        visit[ny][nx][0] = True
                        visit[ny][nx][3] = True
                        if dire==0:
                            q.appendleft((nx,ny,2))
                        else:
                            q.appendleft((nx,ny,1))
                            
                    elif dire == 1 or dire == 2:
                        visit[ny][nx][1] = True
                        visit[ny][nx][2] = True
                        if dire==1:
                            q.appendleft((nx,ny,3))
                        else:
                            q.appendleft((nx,ny,0))

양이 좀 많지만

구조물을 만났을 때 그 방향에 대해서 visit = True로 바꿔준다.

막히면 큐에 추가x, 굴절되면 굴절방향으로 큐에 추가. 가림판 통과면 방문 and 큐에 추가.

방향 dire가 들어왔을 때 dire에 맞는 방향만 탐색한다.

appendleft를 사용해서 한 바람줄기에 대해서 끝까지 탐색하는, DFS처럼 생각해서 구현했다.

3. 출력

count = 0
for i in range(h):
    for j in range(w):
        if any(visit[i][j]):
            count += 1
print(count)

visit 좌표에서 하나라도 True이면 카운팅 해주기

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

aircons = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 9:
            aircons.append((j,i))

q = deque()
step = [(1,0),(-1,0),(0,1),(0,-1)]
visit = [[[False]*4 for _ in range(w)] for _ in range(h)]

for x,y in aircons:
    visit[y][x] = [True]*4
    for i in range(4):
        q.append((x,y,i))

while q:
    x,y,dire = q.popleft()
    
    for i in range(4):
        if i == dire:
            dx,dy = step[i]
            nx = x + dx
            ny = y + dy

            if 0<=nx<w and 0<=ny<h and not visit[ny][nx][i]:
                if arr[ny][nx] == 0:
                    visit[ny][nx][i] = True
                    q.appendleft((nx,ny,dire))
                
                if arr[ny][nx] == 1:
                    if dire == 1 or dire == 0:
                        visit[ny][nx][0] = True
                        visit[ny][nx][1] = True
                    else:
                        visit[ny][nx][2] = True
                        visit[ny][nx][3] = True
                        q.appendleft((nx,ny,dire))
                
                if arr[ny][nx] == 2:
                    if dire == 2 or dire == 3:
                        visit[ny][nx][2] = True
                        visit[ny][nx][3] = True
                    else:
                        visit[ny][nx][0] = True
                        visit[ny][nx][1] = True
                        q.appendleft((nx,ny,dire))
                        
                if arr[ny][nx] == 3:
                    if dire == 0 or dire == 2:
                        visit[ny][nx][0] = True
                        visit[ny][nx][2] = True
                        if dire==0:
                            q.appendleft((nx,ny,3))
                        else:
                            q.appendleft((nx,ny,1))
                            
                    elif dire == 1 or dire == 3:
                        visit[ny][nx][1] = True
                        visit[ny][nx][3] = True
                        if dire==1:
                            q.appendleft((nx,ny,2))
                        else:
                            q.appendleft((nx,ny,0))
                            
                if arr[ny][nx] == 4:
                    if dire == 0 or dire == 3:
                        visit[ny][nx][0] = True
                        visit[ny][nx][3] = True
                        if dire==0:
                            q.appendleft((nx,ny,2))
                        else:
                            q.appendleft((nx,ny,1))
                            
                    elif dire == 1 or dire == 2:
                        visit[ny][nx][1] = True
                        visit[ny][nx][2] = True
                        if dire==1:
                            q.appendleft((nx,ny,3))
                        else:
                            q.appendleft((nx,ny,0))
count = 0
for i in range(h):
    for j in range(w):
        if any(visit[i][j]):
            count += 1
print(count)

코멘트

모듈화 시키는거랑 그냥 복붙이랑 별 차이 없어서 복붙으로 진행.

파이썬 57퍼 초과나서 pypy3로 진행.

이렇게 무식하게 짜는거보다 바람줄기 주변으로 상하좌우만 먼저 탐색하고, 구조물 만났을때만 처리하는게 연산량도 그렇고 문제의도랑 맞는듯

'Algorithm > Graph' 카테고리의 다른 글

[파이썬] 백준 16946 : 벽 부수고 이동하기 4 (골드2) (0)	2023.08.22
[파이썬] 프로그래머스 : 빛의 경로 사이클 (Lv.2) (0)	2023.08.18
[파이썬] 백준 1005 : ACM Craft (골드3) (0)	2023.08.18
[파이썬] 백준 프로그래머스 : 합승 택시 요금 (Lv3) (0)	2023.08.16
[파이썬] 백준 1504 : 특정한 최단 경로(골드4) (0)	2023.08.16
[파이썬] 백준 2481 : 해밍 경로 (골드2) (0)	2023.08.12
[파이썬] 백준 17244 : 아맞다우산 (골드2) (0)	2023.08.09

베짱이의 작업공간

[파이썬] 백준 21922: 학부 연구생 민상 (골드5)