[프로그래머즈 Lv3, Java] 리틀 프렌즈 사천성

리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.

다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.

• 경로의 양 끝은 제거하려는 두 타일이다.
• 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
  • 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
• 경로 상에는 다른 타일 또는 장애물이 없어야 한다.

위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.

타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.

입력 형식

입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.

• 1 <= m, n <= 100
• board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
  • .: 빈칸을 나타낸다.
  • *: 막힌 칸을 나타낸다.
  • 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
  • board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.

출력 형식

해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/1836

프로그래머스

---

 

내가 이 문제를 푼 접근 방식은

1. 단 한 번만 꺾을 수 있다.

 => ㄱ자로 가거나 ㄴ자로 가는 경우가 전부임.

 

2. 같은 글자 타일은 한 쌍씩 있고, 추가로 있거나 부족한 경우는 없음

 => 각 알파벳 별로 매칭되는 두개를 좌표 배열로 만듬

 

3. 여러 경로가 있는 경우 알파벳순으로 정렬

 => 가능한 제일 앞 알파벳부터 탐색함

의 순서대로 구현했다.

 

주저리주저리 설명을 써봤지만 아무래도 그냥 코드를 보는게 제일 빠를 것 같아서 다 지웠다.

 

경로를 검증하는 메소드인 valid를 보면

좌표 Pos1, Pos2가 연결될 수 있는 ㅁ자 경로를 모두 확인한 뒤,

pos1,2가 이루는 직선의 기울기에 따라 사용하는 조합을 바꾼다.

(2차원 좌표계와 달리, 배열에서의 row, col를 의미하므로 직관적이지 못하지만...)

왼쪽은 x,y가 모두 커지는 경우다.

그러므로 변동량이 양수면 SyMx && ExMy) || (SxMy && EyMx를 사용한다.

※S랑 E는 최소, 최대, M은 이동을 의미한다.

 

오른쪽은 x는 증가 y는 감소 하는 경우다.

그러므로 EyEx || SxSy 로 검증한다.