-
백준(BOJ) 2151번 거울 설치알고리즘 풀이/백준(Boj) 2019. 10. 22. 02:22
문제 : https://www.acmicpc.net/problem/2151
2151번: 거울 설치
첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
www.acmicpc.net
풀이 :
#와 !을 정점으로 하고 상하좌우로 거울이나 문이 만날수 있다면 간선을 이어주자.
그 후 처음 #에서 마지막 #으로 가는 최단거리 d를 구하자. 이는 BFS를 이용해서 풀어주자.
ex) 예제
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 2169번 로봇 조종하기 (3) 2019.10.27 백준(BOJ) 14225번 부분수열의 합 (31) 2019.10.25 백준(BOJ) 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (31) 2019.10.18 백준(BOJ) 4연산 (31) 2019.10.16 백준(BOJ) 9944번 NxM 보드 완주하기 (0) 2019.10.13