백준 6087 : 레이저 통신 [파이썬]

https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

1. 문제설명

문제에 풀이에 대한 감을 전혀 잡고 있지 못했다.

생각했던것들은 3가지 였다.

• 벽에 부딪힐 때까지 한방향으로 나아가기       O
• 방향이 바뀔 때 visited + 1처리                        O 
• 3차원 으로 해결                                               X

이 중에서 풀이에 대한 해결법은 2가지 정도만 해당 됐다.

 

이 문제를 푸는 법

• C의 죄표를 찾아 리스트에 좌표값을 넣는다.  (무조건 두개이고 무조건 한쪽에서 한쪽으로 연결된다.)
• 아무거나 한개의 C좌표를 시작점으로 잡고 4방향으로 벽이나 범위 밖으로 벗어날때까지 시작점 + 1 로 visited처리 해주고 queue에 넣고
• 모든 점에서 같은 식으로 나아가기
• visited처리가 안되있거나 출발점 +1 보다 큰 경우에 출발점  + 1 로 visited처리 하면서 진행
• 다른 C에 도착했을 때에 visited 죄표에서 -2 해주며 출력 해주면 레이저가 방향을 꺾는 횟수가 출력된다.

from collections import deque

m, n = map(int, input().split())
board = [list(map(str, input().rstrip())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
C = []
queue = deque()

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    for j in range(m):
        if board[i][j] == 'C':
            C.append((i, j))


queue.append(C[0])
visited[C[0][0]][C[0][1]] = 1
end = C[1]

def bfs():
    while queue:
        x, y = queue.popleft()
        if (x, y) == C[1]:
            print(visited[x][y] - 2)
            break

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            while 0 <= nx < n and 0 <= ny < m:
                if board[nx][ny] == '*':
                    break
                if visited[nx][ny] > visited[x][y]+1 or not visited[nx][ny]:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))

                nx += dx[k]
                ny += dy[k]

bfs()