개요
- 풀이 시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 128 MB
- 기출 : Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO January 2009 Contest > Silver 3번
- 난이도 : 골드 4
- 링크 : https://www.acmicpc.net/problem/6087
문제
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6입력
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.
- .: 빈 칸
- *: 벽
- C: 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
출력
첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
해결방법
문제 이해하기
뭐... 이번 문제를 보자마자 DFS/BFS 그래프 탐색문제라고 생각했다. 그리고 자만했다... 그냥 BFS로 해서 C와 C가 만나도록 탐색을 진행하면서, 동시에 경로가 90도 회전하는 경우는 visited로 해서 기록하면서 최소 값을 찾으면 되지 않을까? 생각했다. (아래 1~N-1차 시도 코드 참고)
알고리즘
솔직히 왜 안되지... 내가 뭐 실수했나 이생각만 계속하면서 틀린 부분을 찾아봤지만 내 코드는 아무런 이상이 없는거 같았다.
하지만 곰곰히 생각해보니 위 같은 상황에서는 내 코드가 제대로 동작하지 않을거 같았다.
# 방문을 했는데 이전 거울개수보다 최솟값이라면
if visited[nx][ny] > cnt:
(...)그니까 내가 했던거는 단순히 위와 같은 로직이었기 때문에 다음 목적지가 어느 방향이냐에 따라서 더 최선의 선택을 골라야 하는데 그러지 못했다.
개선책
위와 같은 생각이 떠오르고 이를 해결하기 위한 방법으로 그냥 visited를 3차원 배열로 만들어서 방향도 따로 관리를 해주자는 것이었다.
visited = [[[INF] * 4 for _ in range(w)] for _ in range(h)] # ✅
# 방문을 했는데 이전 거울개수보다 최솟값이라면
if visited[nx][ny][i] > cnt:
(...)
return min(visited[ex][ey])이렇게 하면 방향에 따라서 최소값을 결정할 수 있기 때문에 결과를 얻어낼수 있었다.
더 쉬운 방법
찾아보니 더 쉽고 효율적인 방법이 있었다. BFS를 통해서 탐색을 진행하되 한 방향을 정했으면 그 방향으로 쭉 탐색을 하는 방식이다.
def bfs(x,y):
queue = deque([(x,y)])
visited[x][y] = 0
while queue:
x,y = queue.popleft()
for i in range(4):
## 동 남 서 북 순서
nx, ny = x+dx[i], y+dy[i]
while True:
## 범위를 벗어난다
if not(0<=nx<n and 0<=ny<m): break
## 벽을 만난다
if board[nx][ny]=='*': break
## 지난 적 있는 곳인데, 지금 경로로는 너무 많은 거울이 필요해서 break
if visited[nx][ny] < visited[x][y]+1: break
## board업데이트, queue 추가
queue.append((nx,ny))
visited[nx][ny] = visited[x][y] + 1
nx = nx+dx[i]
ny = ny+dy[i]코드를 보면 이해가 갈 것이다. 최선의 결과를 위해 한방향으로 쭉 탐색하고, 그 다음 방향에서도 그 방향으로 쭉 탐색하는 방식. (개쩐다... 이걸 생각 못했네)
Python
1~N-1차 시도
from collections import deque
import sys
input = sys.stdin.readline
INF = int(1e9)
# 서-북-동-남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
def bfs(sx, sy, ex, ey):
q = deque()
visited = [[INF] * w for _ in range(h)]
# 초기에 이동가능한 경로
for i in range(4):
nx = sx + dx[i]
ny = sy + dy[i]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
q.append((nx, ny, i))
visited[nx][ny] = 0
while q:
x, y, direct = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
cnt = visited[x][y]
if direct == 0 or direct == 2:
if i == 1 or i == 3:
cnt += 1
else:
if i == 0 or i == 2:
cnt += 1
if visited[nx][ny] == INF: # 방문한 적이 없음
visited[nx][ny] = cnt
q.append((nx, ny, i))
else: # 방문을 했는데 이전 거울개수보다 최솟값이라면
if visited[nx][ny] > cnt:
visited[nx][ny] = cnt
q.append((nx, ny, i))
return visited[ex][ey]
if __name__ == "__main__":
w, h = map(int, input().split())
pos = []
board = []
for i in range(h):
board.append(list(input().strip()))
for j in range(w):
if board[i][j] == "C":
pos.append((i, j))
print(bfs(pos[0][0], pos[0][1], pos[1][0], pos[1][1]))
N차 시도
from collections import deque
import sys
input = sys.stdin.readline
INF = int(1e9)
# 서-북-동-남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
def bfs(sx, sy, ex, ey):
q = deque()
visited = [[[INF] * 4 for _ in range(w)] for _ in range(h)] # ✅
for i in range(4):
nx = sx + dx[i]
ny = sy + dy[i]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
q.append((nx, ny, i))
visited[nx][ny][i] = 0
while q:
x, y, direct = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
cnt = visited[x][y][direct]
if direct == 0 or direct == 2:
if i == 1 or i == 3:
cnt += 1
else:
if i == 0 or i == 2:
cnt += 1
if visited[nx][ny][i] == -1: # 방문한 적이 없음
visited[nx][ny][i] = cnt
q.append((nx, ny, i))
else: # 방문을 했는데 이전 거울개수보다 최솟값이라면
if visited[nx][ny][i] > cnt:
visited[nx][ny][i] = cnt
q.append((nx, ny, i))
return min(visited[ex][ey])
if __name__ == "__main__":
w, h = map(int, input().split())
pos = []
board = []
for i in range(h):
board.append(list(input().strip()))
for j in range(w):
if board[i][j] == "C":
pos.append((i, j))
print(bfs(pos[0][0], pos[0][1], pos[1][0], pos[1][1]))
추천 코드
from collections import deque
def bfs(x, y):
queue = deque([(x, y)])
visited[x][y] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
## 동 남 서 북 순서
nx, ny = x + dx[i], y + dy[i]
while True:
## 범위를 벗어난다
if not (0 <= nx < n and 0 <= ny < m):
break
## 벽을 만난다
if board[nx][ny] == "*":
break
## 지난 적 있는 곳인데, 지금 경로로는 너무 많은 거울이 필요해서 break
if visited[nx][ny] < visited[x][y] + 1:
break
## board업데이트, queue 추가
queue.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
nx = nx + dx[i]
ny = ny + dy[i]
print(visited)
if __name__ == "__main__":
## 입력값
m, n = map(int, input().split())
board = [input() for _ in range(n)]
## 동 남 서 북
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
## C위치
C = []
for i in range(n):
for j in range(m):
if board[i][j] == "C":
C.append((i, j))
## sx,sy : 시작지점
## ex,ey : 도착지점
(sx, sy), (ex, ey) = C
visited = [[float("inf")] * m for _ in range(n)]
bfs(sx, sy)
print(visited[ex][ey] - 1)
# 코드 참고 : https://www.acmicpc.net/source/27251914✍️ 쉽게 생각했던 문제가 뒤통수를 쳤네..;; 왜 정답비율이 30% 인지 알거 같다.
