[프로그래머스] - 프렌즈4블록

문제

 

입출력 형식

 

입출력 예제

 

솔루션

• 좌표를 저장할 Point 클래스를 만든다. 중요한 점은 오버라이딩 함수들이다.
  • hashCode()와 equals() 함수인데, 오버라이딩 한 이유는 Point 객체끼리 동일한 객체 비교가 아닌 동일한 좌표인지 비교할 수 있도록 하기 위함이다.
  • hashCode() & equals() - https://soobarkbar.tistory.com/94
•  사용한 변수들 :
  • rmlist - HashSet 자료구조이며, 부술 블록들을 저장해 놓을 객체 변수이다.
  • chrboard - 주어진 String형 배열 board를 char형으로 좀 더 편리하게 다루기 위한 2차원 배열이다.
  • canBreak - 아직 부술 블록들이 남아있는가 (4개 묶음 블록이 존재하는가) 를 판단하고 게임을 계속 진행할지 여부를 담아놓은 boolean 변수이다.
  • BFS를 사용하였지만 방문 여부를 체크하는 boolean[][] visited 변수를 사용하지 않았다.
    • Why ?) 4개씩 묶어서 블록들이 제거가 되는데 4개 묶음 블록이 겹치는 경우 (아래), 이미 앞에서 방문했다는 표시를 하게 되면 다음 번에 해당 블록을 건너뛰고 4개인지 체크를 할 것이고 실제로 부술 수 있는 블록들이지만 갯수가 부족하여 블록을 부수지 않는다.

1. 입력 값인 board를 chrboard의 0 인덱스 부터 순서대로 다루기 위해 거꾸로 집어넣는다.
2. 부술 블록들이 아직 남아있는지를 canBreak로 확인하며, while 루프를 계속 수행한다.
   1. chrboard의 모든 좌표를 탐색하며 4개 묶음 블록이 있는지를 확인하는 함수를 반복문을 수행한다.
      
      1. chrboard[x][y]가 '.' 이라면 (블록이 부서진 빈공간), 다음 좌표로 이동한다.
      2. '.'이 아니라면, 4개 묶음 블록을 찾기 위해 Find4Block 메소드를 실행한다.
   2. 완전 탐색을 마치고 반복문을 빠져나온 뒤, 부술 블록들이 있는지 확인한다 (rmlist가 비어있는가).
   3. rmlist가 비어 있지 않다는 것은 부숴야 할 4개 묶음 블록이 있는 것이므로, 계속해서 블록들을 확인하기 위해 canBreak를 true로 갱신한다.
   4. 또한, rmlist에 담겨있는 좌표의 블록들을 부수면 되기 때문에 Break4Block 메소드를 실행한다.
   5. 블록을 부순 뒤, 블록들을 아래로 내리기 위해 DownBlock 메소드를 실행한다.
   6. rmlist가 비어 있다는 것은 더이상 부술 블록이 없기 때문에 canBreak가 true로 갱신되지 못하고 while문을 빠져나가고 종료한다.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_friends4block.java

좌표를 저장할 클래스 (Point)

부수려고 하는 4개의 블록을 찾는 함수 (Find4Block)

1. 전달받은 파라미터 :
   • rmlist (부숴야할 블록들의 좌표, 중복을 허용하지 않음)
   • chrboard (각 좌표에 들어있는 블록의 종류)
   • start (블록을 찾을 시작 좌표)
2. 변수 :
   • dx, dy : 시작 좌표를 기준으로 오른쪽, 아래, 대각선 위치의 블록 (아래 그림) 을 확인할 수 있도록 더해주는 값이다.
   • nx, ny : Start의 다음 좌표 (Start.x, Start.y에 각각 dx[i], dy[i]를 더한 값) 인 오른쪽, 아래, 대각선 좌표이다.
   • list : nx, ny가 시작 포인트와 동일한 종류의 블록일 때, 잠시 담아놓는 ArrayList 객체이다.

1. 먼저 시작포인트 start를 리스트에 집어넣는다.
2. 그리고 세 군데 방향으로 확인하며, 시작포인트와 동일한 종류의 블록인지 확인하는 반복문을 수행한다.
   1. 만약 동일하다면, list에 블록의 좌표를 삽입한다.
   2. 동일하지않다면, 해당 반복문을 빠져나온다.
3. list의 크기가 4라면 (모두 동일한 종류의 블록이라는 것), rmlist에 list에 존재하는 좌표들을 옮겨 담는다.
4. 그런데, 여기서 중요한 점은 rmlist에 이미 존재하는 좌표 (중복된다면, contains() 메소드를 이용) 라면, 다음 좌표로 넘어간다는 것 (중복을 허용하지 않아야 하므로) 이다.
   • 만약 동일한 좌표가 2개이상 있다면, 영역의 넓이가 중복된 갯수만큼 넓어질 것이다.
   • 이 부분에서 오버라이딩한 메소드들이 효력을 발휘하는 것이다. (equals(), hashCode())

 

찾은 블록들을 부수는 함수 (Break4Block)

• 부술 블록들의 좌표가 담겨 있는 rmlist를 iterator()를 통해 처음부터 끝까지 조회하며 각 좌표들의 문자를 '.'으로 갱신한다.
• 그리고 rmlist를 깨끗이 비워준다.

 

블록들을 아래로 내리는 함수 (DownBlock)

• 블록을 부수고 난 뒤, 블록들을 아래로 내려 빈 공간을 채우기 위한 함수이다.
• 과정은 아래와 같다.

1. 완전 탐색으로 chrboard를 조회하는데, 행 -> 열이 아닌, 열 -> 행으로 반복문을 진행한다.
   • Why ?) 블록이 위에서 아래로 떨어지는 것은 동일한 열에서 행이 줄어드는 것이기 때문이다.
2.  반복문 수행 내용은 다음과 같다.
   1. 블록이 비어있지 않다면 큐에 삽입하고, 비어있다면 ('.'이라면), 큐에 삽입하지 않는다.
   2. 큐에 삽입된 블록들을 하나씩 꺼내며, idx행 (처음은 0) 에 문자를 갱신하고 idx를 1증가시킨다.
   3. 2번의 과정을 큐가 빌때까지 진행한다.
   4. 다음으로 총 행 길이 (chrboard.length) 에서 idx를 빼면 나머지 비어있는 블록들의 갯수가 나오므로, idx부터 총 행 길이까지의 chrboard는 '.'으로 갱신한다.

 

메인 Solution 함수

 

결과