[백준 / BOJ] 11067 모노톤 길

문제

출처 : www.acmicpc.net/problem/11067

11067번: 모노톤길

산책코스가있다.

산책코스에는 코너마다 카페가있고, 코스관리자인 김씨는 산책로를 따라갈때 (X,Y)에있는 카페를 몇번째로 방문하는지 알고싶다.

 

n개의 카페 위치(X,Y)가 주어졌을때 카페를 몇번 반복하는지 찾는 문제다.

단, X를 줄일필요없이 항상 모든카페를 방문할수있고, 같은 번호를 갖는 카페는 없다.

모든 코너에서는 90도로 회전해서 이동만할수있다.(대각선 이동이 안됨.)

 

풀이

우선, 제한시간이 5초다.

T의 갯수에 따라서 다르겠지만, n이 최대 10만이므로 완전탐색으로도 풀리는 문제다.

 

'X를 줄일필요없이 항상 모든카페를 방문할수있다' 이 조건이 있기때문에,

현재위치(X,Y)에서 가장 가까운 거리에 있는 카페를 선택해서 가야지만 모든카페를 순서대로 방문할수있다. (되돌아 가서 방문할수 없으므로)

 

방문 순서는

1. 현재 위치와 같은 열에있는 (X가 같은) 카페들중 가장 가까운 카페로 이동한다.

만약 같은 열에있는 모든 카페를 방문하지않은상태로 같은 행에있는 (Y가같은) 가장 가까운 카페로 이동하면, X를 줄일수없으므로 안된다.

2. 같은 열에있는 모든 카페를 전부 방문했다면, 같은 행에있는 가장 가까운 정점으로 이동한다. 

같은 열에있는 모든카페를 방문했을때, 현재 위치와 같은 행에는 무조건 하나이상의 카페가 존재한다. 만약 존재하지 않는다면 대각선 이동이 안되고 왔던길을 되돌아갈수없으므로 모든카페를 방문할수 없다.

매 방문마다 카페의 방문순서를 저장해준다. 

 

위 두가지를 반복하면 모든카페의 방문순서를 알수있다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11067%20%EB%AA%A8%EB%85%B8%ED%86%A4%EA%B8%B8/main.cpp

devxb/JJUNalgo