문제 바로가기
문제:
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
입력:
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다. .: 빈 칸 *: 벽 C: 레이저로 연결해야 하는 칸 'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
출력:
첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
풀이:
80프로 에서 시간초과
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
m, n = map(int,sys.stdin.readline().split(" "))
graph =[list(sys.stdin.readline()) for _ in range(n)]
spot = []
for i in range(n):
for j in range(m):
if graph[i][j] == "C":
spot.append((i,j))
start = spot[0] ; end = spot[1]
move = [(0,1),(0,-1),(1,0),(-1,0)]
count = 0; dir = -1
Q = deque()
Q.append((count,dir,start[0],start[1]))
visited = [[float("inf")] * m for _ in range(n)]
visited[start[0]][start[1]] = 0
while Q:
# 거울수, 방향, 현재 x위치, 현재 y위치
count, direction, x, y = Q.popleft()
# 목적지 도착했을때
if x == end[0] and y == end[1]:
# 거울 뽑고 종료
print(count)
exit()
# 들린적 있지만 더 적은 갯수로 방문 한 적 있음
if visited[x][y] < count:
continue
# 거울 추가하나 하고 돌려봄
visited[x][y] = count
for I in range(4):
nx = x + move[I][0]
ny = y + move[I][1]
#범위 내에 위치하고 벽을 만난 것이 아님
if 0 <= nx < n and 0<= ny < m and graph[nx][ny] != "*":
# 같은 방향으로 나아가거나, 맨 처음이라 어디 방향으로 갈지 안정함
if I == direction or direction == -1:
# 처음으로 나오게 해야함, 가장 최솟값을 구해야 하기 떄문에
Q.appendleft((count,I,nx,ny))
# 꺽어야 하는 경우
else:
Q.append((count+1,I,nx,ny))
정답 코드
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
m, n = map(int,sys.stdin.readline().split(" "))
graph =[list(sys.stdin.readline()) for _ in range(n)]
spot = []
for i in range(n):
for y in range(m):
if graph[i][y] == "C":
spot.append((i,y))
start = spot[0] ; end = spot[1]
move = [(0,1),(0,-1),(1,0),(-1,0)]
Q = deque()
Q.append((start[0],start[1]))
visited = [[1e9] * m for _ in range(n)]
visited[start[0]][start[1]] = -1
while Q:
x, y = Q.popleft()
# 목적지 도착
if x == end[0] and y == end[1]:
# 거울 뽑고 종료
print(visited[x][y])
break
for dx, dy in move:
nx, ny = x + dx, y + dy
#범위 내에 위치하면서, 벽이 아니고, 거울 안 쓴게 더 좋음
while 0 <= nx < n and 0 <= ny < m and not graph[nx][ny] == "*" and visited[x][y] < visited[nx][ny]:
if visited[nx][ny] == visited[x][y] + 1:
nx, ny = nx + dx, ny + dy
continue
# 거울 설치
visited[nx][ny] = visited[x][y] + 1
# 다음 방향 큐에 추가
Q.append((nx,ny))
nx, ny = nx + dx, ny + dy
굉장히 어려워서 다른 사람풀이도 좀 보면서 했다.
다른 코드들은 방향을 3차원배열로 저장하던가, 따로 direct 리스트를 만들어서 관리하는 사람도 있다.
일단 visited[start[0]][start[1]] = -1 로 시작지점을 -1 로 선언 해준다.
그 다음 while 문 안에 for 문 안에 while 문이 문제인데
while 0 <= nx < n and 0 <= ny < m and not graph[nx][ny] == "*" and visited[x][y] < visited[nx][ny]:범위내에 위치하면서, 다음 좌표가 벽이 아니고, 현재위치가 다음 위치 방문하는 시간보다 적을 경우이다. 초기값은 1ㄷ9 방문을 하지 않은 상태일때 까지 진행한다.
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......이거로 예시를 들을때 처음 start = [1,6] visited[1][6] = -1 이다.
그럼 [1][6] 기준 왼쪾으로 쭉, 위로 한개 갈수 있다,
7 8
......ㅣ
------C
......*
*****.*
....*..
....*..
.C..*..
.......
[1,6] C 기준 왼쪽, 위 는 거울이 필요없다. 그래서 C가 처음에 -1 인 이유이다 .
7 8
......0
000000C(-1)
......*
*****.*
....*..
....*..
.C..*..
.......그러면 0인 것들이 (nx,ny) 가 돼서 처음 Q 에 들어간 visited[1][6] = -1 을 빼 거기에 +1 된 0 값들이
while문을 못 빠져나가고visited 가 최신화 된다.
while 0 <= nx < n and 0 <= ny < m and not graph[nx][ny] == "*" and visited[x][y] < visited[nx][ny]:
if visited[nx][ny] == visited[x][y] + 1:
nx, ny = nx + dx, ny + dy
continue위에는 거울을 설치하지 않는경우라고 볼 수 있다.
if문이 없으면 80프로에서 시간초과로 끝이난다. 그 이유는 탐색은 완료 했는데 다시 방문하는 경우가 있다.
visited[nx][ny]가 이미 방문한 시간 visited[x][y]보다 작은 경우라면, 이미 더 짧은 경로를 찾았음에도 불구하고 더 오래 걸리는 경로를 계속 탐색하기 때문이다. 이미 1개 추가해서 방문할 수 있는 위치라면 직진한다 .
cf) == 을 <= 으로 바꿔줘도 정답이된다
그럼 그 다음은 거울을 설치하는경우
저 그림으로 미리 해보겠다
7 8
1111110
000000C(-1)
111111*
*****1*
....*1.
....*1.
.C..*1.
.....1.이렇게 되는것이다. 왜그러냐 !?
지금 0인 좌표의 x,y 값 들이 Q에 append 되어있다
Q = deque([(1, 5), (1, 4), (1, 3), (1, 2), (1, 1), (1, 0), (0, 6)])
이렇게 들어있게된다. 그럼 이것들도 똑같이 상화좌우 다 더한후 체크를 하게 된다.
최소힙으로 어떻게 푸는지도 봐보겠다.
댓글