JB의 이모저모
[BOJ 15559 🥇2] 내 선물을 받아줘 (Python) 본문
https://www.acmicpc.net/problem/15559
문제
욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.
구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다.
지도의 각 칸에는 N, W, E, S 중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (i, j)인 경우에 N이 쓰여져 있는 칸에 서 있었다면, (i-1, j)로, S의 경우에는 (i+1, j)로, W의 경우에는 (i, j-1), E의 경우에는 (i, j+1)로 순간이동한다. 구사과는 지치지 않기 때문에, 계속해서 이동한다.
욱제는 구사과의 위치를 모르기 때문에, 구사과가 이동을 시작하는 위치와 관계없이 선물을 주는 방법을 알아내려고 한다. 최소 몇 개의 칸 위에 선물을 놓으면, 구사과가 항상 선물을 가져가는지 구하는 프로그램을 작성하시오. 선물이 놓여진 칸에 구사과가 이동하면, 구사과는 항상 선물을 가져간다.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000)
둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다.
지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.
출력
첫째 줄에 최소 몇 개의 칸에 선물을 놓아야 하는지 출력한다.
예제 입력 1
3 4
SWWW
SEWN
EEEN
예제 출력 1
2
⭕ CODE
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs(x, y):
global group
q = deque()
q.append((x, y))
# 방문처리를 group으로 처리
visited[x][y] = group
while q:
x, y = q.popleft()
# 현재 위치가 s 라면 아래로 이동
if arr[x][y] == 'S':
# 아래가 방문한적이 없다면
if visited[x + 1][y] == 0:
# q에 담아주고 다음 위치를 group으로 방문처리
q.append((x + 1, y))
visited[x + 1][y] = group
# 아래로 이동했는데 지금 group보다 작다면
# 이전에 방문했었다. 즉 하나의 그룹으로 가능하므로 추가 그룹이 없다
# 0 반환
elif visited[x + 1][y] < group:
return 0
elif arr[x][y] == 'E':
if visited[x][y + 1] == 0:
q.append((x, y + 1))
visited[x][y + 1] = group
elif visited[x][y + 1] < group:
return 0
elif arr[x][y] == 'N':
if visited[x - 1][y] == 0:
q.append((x - 1, y))
visited[x - 1][y] = group
elif visited[x - 1][y] < group:
return 0
elif arr[x][y] == 'W':
if visited[x][y - 1] == 0:
q.append((x, y - 1))
visited[x][y - 1] = group
elif visited[x][y - 1] < group:
return 0
# 다 했는데도 기존 그룹이 없다면 새로운 그룹이므로
# 1 반환
return 1
n, m = map(int, input().split())
arr = [list(input()) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
# 선물의 개수 count
count = 0
# 그룹의 개수 group
group = 0
for i in range(n):
for j in range(m):
# 방문한적이 없으면
if visited[i][j] == 0:
# 그룹 1 추가
group += 1
# bfs의 결과를 count에 추가
count += bfs(i, j)
print(count)
✏️ Comment
합쳐져서 그룹이 하나가 되는 부분을 생각하는것이 조금 어려웠던 문제이다.
그래서 bfs를 돌릴때 방문처리를 group으로 지정하여 현재 그룹과 비교하는 방식을 사용하였다
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ 14627 🥈2] 파닭파닭 (Python) (0) | 2024.01.03 |
---|---|
[BOJ 3649 🥇5] 로봇 프로젝트 (Python) (0) | 2024.01.03 |
[BOJ 2412 🥇4] 암벽 등반 (Python) (0) | 2024.01.03 |
[BOJ 5213🥇2] 과외맨 (Python) (0) | 2023.12.29 |
[BOJ 16985🥇2] Maaaaaaaaaze (Python) (1) | 2023.12.15 |