프로그래머스/위클리 챌린지/퍼즐 조각 채우기

https://programmers.co.kr/learn/courses/30/lessons/84021

 

풀이

- 보드 빈칸에 회전시킬 수 있는 조각을 채워넣어야 한다

- 최대한 많은 조각을 채워넣고, 몇 칸을 채웠는지 출력하면 된다

 

- 보드에 어떤 위치에 조각이 들어있는지는 상관 없다. 모양이 맞기만 하면 되는거라 "빈 칸"과 "조각들"만 구분하면 된다.

- 해당 빈 칸과 같은 모양의 조각이 있는지 회전해가며 찾으면 된다.

- 어려운 부분은 "조각을 골라내기"이다.

---

1) 조각을 골라내는 방식 정하기



조각을 떼어내려면 각 칸의 연결성을 알아내야 한다.

나는 맨 첫번째 칸부터 시작해서 우측으로 이동하며 연결성을 알아보기로 했다.

이 경우 좌측, 상단의 칸만 조사하면 되기 때문이었다.

다만, 우측으로 연결되었음에도 불구하고 좌측과 상단이 빈 경우가 있었다.

 

이 경우는 일단 분리된 조각으로 판단했다.

그 후, 좌측과 상단을 조사했을 때 서로 다른 블록을 가리키는 경우가 있다면 해당 블록들을 통합했다.

어느 좌표가 어떤 블록에 포함되어있는지 빠른 검색을 위해 Dictionary를 이용했고,

블록 객체에서는 해당 객체에 포함된 좌표들을 해시셋으로 보관했다.

---

2) 조각을 int[,] 데이터로 변환하고, 회전하면서 맞추기

조각을 골라냈다면 이후는 간단하다. 2차원 배열을 회전시키면서 맞추기만 하면 되기 때문이다.

참고로 테이블에 있던 조각들 중에서 이미 끼워 넣은 것들을 제외시키지 않으면 틀리게 될 것이다 (...) 경험담.

 

 

C#

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] game_board, int[,] table) {
        
        int answer = 0;
        
        var GameBoard = new board(game_board, 0).Get_Blocks();
        var Table = new board(table, 1).Get_Blocks();

        foreach(var board_block in GameBoard) {
            
            int[,] finded = null;
            
            foreach(var table_block in Table) {
                
                if(isEqual(board_block, table_block)) {
                    finded = table_block;
                    break;
                }
                
                else {
                    int[,] rotated = table_block;
                    
                    for(int i=0; i<3; i++) {
                        rotated = Rotate90(rotated);
                        if(isEqual(board_block, rotated)) {
                            finded = table_block;
                            break;
                        }
                    }
                }
            }
            
            if(finded != null) {
                answer 
                += board_block.Cast<int>().Count(e => e == 1);
                
                Table.Remove(finded);
            }
        }
        
        return answer;
    }
    
    public int[,] Rotate90(int[,] data) {
        
        int width = data.GetLength(1);
        int height = data.GetLength(0);
        int[,] result = new int[width, height];

        for(int i=0; i<width; i++){
            for(int j=0; j<height; j++){
                result[i, j] = data[j, width-i-1];
            }
        }
        
        return result;
    }

    private bool isEqual(int[,] A, int[,] B) {
        bool result = true;
        
        if(A.GetLength(0) != B.GetLength(0) 
           || A.GetLength(1) != B.GetLength(1)) return false;
        
        for(int i=0; i<A.GetLength(0); i++){
            for(int j=0; j<A.GetLength(1); j++){
                if(A[i, j] != B[i, j]){
                    result = false;
                    break;
                }
            }
        }
        
        return result;
    }
}


public class board {

    public Dictionary<Vector2, Block> Map;
    
    public board(int[,] data, int validValue) { 
        Map = new Dictionary<Vector2, Block>();
        Initialize(data, validValue);
    }
    
    public void Initialize(int[,] data, int validValue) {
        
        int size = data.GetLength(0);

        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                
                Vector2 key = new Vector2(i, j);
                
                if(data[key.x, key.y] == validValue && !Map.ContainsKey(key))
                    connect(getConnectedBlock(key), key);
            }
        } 
    }
    
    public List<int[,]> Get_Blocks() {
        
        var result = new List<int[,]>();
        
        foreach(var block in Map.Values.Distinct()) {
            result.Add(block.ToArray());
        }
        
        return result; 
    }
    
    private void connect(Block block, Vector2 key){
        block.Add(key);
        Map.Add(key, block);
    }
    
    private Block getConnectedBlock(Vector2 key) {
        var leftKey = new Vector2(key.x, key.y - 1);
        var upKey = new Vector2(key.x - 1, key.y);
        
        var left = Map.ContainsKey(leftKey) ? Map[leftKey] : null;
        var up = Map.ContainsKey(upKey) ? Map[upKey] : null;

        if(left != up && left != null && up != null) combine(left, up);
        
        if(left != null) return left;
        else if(up != null) return up;
        else return new Block();
    }
    
    private void combine(Block a, Block b){
        foreach(var e in b.List) { 
            a.List.Add(e);
            Map[e] = a;                    
        }
    }
}

public class Block {
    public HashSet<Vector2> List 
        = new HashSet<Vector2>();
    
    public void Add(Vector2 key) {
        List.Add(key);
    }
    
    public int[,] ToArray() {
        var pivotX = List.Min(e => e.y);
        var pivotY = List.Min(e => e.x);

        var width = List.Max(e => e.y) - pivotX + 1;
        var height = List.Max(e => e.x) - pivotY + 1;

        var result = new int[height, width];

        foreach(var e in List)
            result[e.x - pivotY, e.y - pivotX] = 1;

        return result;
    }
}

public struct Vector2 {
    public int x, y;
    public Vector2(int x, int y) { this.x = x; this.y = y;}
}

 

결과

100.0/100.0

피드백

해결하는데 너무 오래 걸렸다. 일단 조각을 골라낼 때 삽질을 너무 많이 함.

하지만 내가 C#으로 제일 처음 해결한 사람이라서 매우 뿌듯함. 젠장! 이 맛에 하는 거로군!

 

그리고 더러운 코드라고 느껴서 리팩터링을 시도(...)했었는데, 제일 처음으로 정답이었던 코드만 기록되서 과감히 버렸다.

다음엔 코딩테스트 문제는 풀고 나서 리팩터링하지 말아야겠다. 그럴 시간에 내 프로젝트 코드나 리팩터링하라고 ^w^...