백준 6087번 문제 링크: https://www.acmicpc.net/problem/6087
문제
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
📑 문제 설명
w, h 사이즈 그래프가 주어진다. 빈 공간인 '.'와 벽인 '*', 그리고 'C' 2개로 구성되어 있다. 문제에서는 'C'와 'C' 사이를 레이저로 통신할 때 필요한 최소 거울의 개수를 출력해야 한다.
입력: w, h / 그래프 모양
출력: 레이저 통신 시 필요한 최소 거울의 개수
💡 문제 해결 방법
처음에는 빈 공간에 하나씩 거울을 설치하고 연결 가능성을 조사해야 하나 싶었으나 단순 bfs로 풀이가 가능하다.
여기서의 핵심은 지금까지 진행하던 방향과 다음 칸으로 가는 방향 간의 차이가 있는지 조사해야 한다.
때문에 우리가 bfs 시 q에 넣는 정보 x, y외에 추가적으로 거울의 개수, 현재 방향 정보를 추가해서 총 4가지 정보를 append해야 한다.
또한 방향별 거울의 개수를 저장하는 리스트를 따로 만들어야 한다. 이때 리스트는 단순 2차원이 아닌 4차원(이나?) 배열로 만들어야 한다.
💻 코드
def reverse_sentence(sentence):
temp_word = list()
result_word = list()
for i in range(0, len(sentence)):
if (sentence[i] != ' '):
temp_word.append(sentence[i])
elif (sentence[i] == ' '):
for j in range(len(temp_word)-1, -1, -1):
result_word.append(temp_word[j])
result_word.append(' ')
temp_word.clear()
if (i == (len(sentence) - 1)):
for j in range(len(temp_word)-1, -1, -1):
result_word.append(temp_word[j])
temp_word.clear()
return result_word
if __name__ == '__main__':
t = input()
for i in range(int(t)):
setence = input()
result_word = "".join(reverse_sentence(setence))
print(result_word)
