< 프로그래머스 LV3 퍼즐 조각 체우기 >
키워드 : BFS + 사고
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
int[] dx = new int[] { 0, 0, 1, -1 };
int[] dy = new int[] { 1, -1, 0, 0 };
List<List<Tuple<int, int>>> boardList = new List<List<Tuple<int, int>>>();
List<List<Tuple<int, int>>> tableList = new List<List<Tuple<int, int>>>();
public int solution(int[,] game_board, int[,] table)
{
bool[,] boardVisited = new bool[game_board.GetLength(0), game_board.GetLength(1)];
bool[,] tableVisited = new bool[table.GetLength(0), table.GetLength(1)];
ExtractBlock(game_board, boardList, boardVisited, 0); // 빈칸 찾기
ExtractBlock(table, tableList, tableVisited, 1); // 블록 찾기
return MatchBlocks();
}
void ExtractBlock(int[,] targetBoard, List<List<Tuple<int, int>>> targetList, bool[,] visited, int checkNum)
{
for (int i = 0; i < targetBoard.GetLength(0); i++)
{
for (int j = 0; j < targetBoard.GetLength(1); j++)
{
if (targetBoard[i, j] == checkNum && !visited[i, j])
{
BFS(targetBoard, targetList, visited, j, i, checkNum);
}
}
}
}
void BFS(int[,] targetBoard, List<List<Tuple<int, int>>> targetList, bool[,] visited, int startX, int startY, int checkNum)
{
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((startX, startY));
List<Tuple<int, int>> list = new List<Tuple<int, int>>();
while (queue.Count > 0)
{
(int nowX, int nowY) = queue.Dequeue();
visited[nowY, nowX] = true;
list.Add(new Tuple<int, int>(nowX, nowY));
for (int i = 0; i < 4; i++)
{
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
if (nextX < 0 || nextX >= targetBoard.GetLength(1))
continue;
if (nextY < 0 || nextY >= targetBoard.GetLength(0))
continue;
if (visited[nextY, nextX] || targetBoard[nextY, nextX] != checkNum)
continue;
visited[nextY, nextX] = true;
queue.Enqueue((nextX, nextY));
}
}
SetPivot(targetList, list);
}
void SetPivot(List<List<Tuple<int, int>>> targetList, List<Tuple<int, int>> setList)
{
int minX = setList.Min(p => p.Item1);
int minY = setList.Min(p => p.Item2);
List<Tuple<int, int>> pivotList = setList.Select(p => new Tuple<int, int>(p.Item1 - minX, p.Item2 - minY)).ToList();
pivotList = pivotList.OrderBy(p => p.Item1).ThenBy(p => p.Item2).ToList();
targetList.Add(pivotList);
}
List<Tuple<int, int>> Rotate(List<Tuple<int, int>> inputList)
{
List<Tuple<int, int>> rotatedList = inputList.Select(p => new Tuple<int, int>(-p.Item2, p.Item1)).ToList();
int minX = rotatedList.Min(p => p.Item1);
int minY = rotatedList.Min(p => p.Item2);
return rotatedList.Select(p => new Tuple<int, int>(p.Item1 - minX, p.Item2 - minY)).OrderBy(p => p.Item1).ThenBy(p => p.Item2).ToList();
}
int MatchBlocks()
{
int filledCount = 0;
List<bool> usedTableBlocks = new List<bool>(new bool[tableList.Count]);
foreach (var boardBlock in boardList)
{
for (int i = 0; i < tableList.Count; i++)
{
if (usedTableBlocks[i]) continue;
var tableBlock = tableList[i];
for (int r = 0; r < 4; r++)
{
if (boardBlock.SequenceEqual(tableBlock))
{
filledCount += boardBlock.Count;
usedTableBlocks[i] = true;
break;
}
tableBlock = Rotate(tableBlock);
}
if (usedTableBlocks[i]) break;
}
}
return filledCount;
}
}
정말로 오랜시간 생각하고 추가적인 팁도 찾아봤어야 했던 문제였습니다.
이 문제의 핵심 요소는 아래와 같습니다.
- BFS를 이용해서 borad와 table에서 조각 뜯어내기.
- 해당 조각은 pivot에 맞춰서 위치를 재조정하기.
- (0,0)을 기준으로 90도씩 회전할 수 있는 함수 만들기.
- 모든 board를 돌면서 table과 완전히 일치하는 조각이 있는지 찾기.
여기서 가장 큰 문제는 조각을 뜯어내서 회전시킬때, 어떻게 하면 동일한 조각인지 맞출 수 있냐는 것이었습니다.
제가 팁을 찾아봤던 부분이 이 부분으로써, 각각 x의 최소값과 y의 최소값을 찾아, 그만큼을 모든 좌표에서 빼주는 것으로 pivot을 맞춰주게 됩니다. 이것이 회전과 어떻게 일치하여 각각의 좌표를 비교할 수 있는지의 예시는 아래와 같습니다.
가장 이해하기 쉽게 직접 그림을 그려 본 모습으로, 회전은
( x , y ) => ( -y , x )
가 되는 것을 말합니다
즉, x y 각각의 최소값을 찾아 이를 0,0 으로 바꿀 수 있도록 pivot을 설정하게 되면 90도를 회전하더라도 동일한 좌표가 나오게 되는 것을 볼 수 있었습니다.
추가적으로 기존에는 foreach문을 통해서 매번 빈칸과 조각을 비교하였으나
SequenceEqual()
를 사용하면 좀 더 보귀 쉽게 컬랙션이 같은 순서와 크기의 요소들을 가지고 있는지 비교할 수 있다는 사실을 알게 되었습니다.
마지막으로 이 문제의 풀이에 사용된 함수들을 정리해보면 아래와 같습니다.
ExtractBlock() : 이중 for문을 돌면서 아직 찾아내지 않는 조각을 BFS로 넘김니다.
BFS : 깊이 우선 탐색을 돌면서 해당 요소와 연관된 조각들을 모으고, 마지막에 Pivot을 설정하는 험수로 전달합니다.
Pivot : 전달 받은 튜플 리스트에서 최소x, 최소y 를 찾은 후 모든 요소에 빼 위치를 조정합니다.
Rotate : 90도씩 리스트를 회전시킵니다. 회전 후에는, Pivot이 다시 0,0이 될 수 있도록 앞선 조정을 반복합니다.
MatchBlocks : 최대한으로 체울수 있는 조각의 수와, 그 때의 칸 수를 계산해 반환합니다. 이때, 이미 사용한 조각인지 체크하는것이 중요합니다.
< 프로그래머스 LV2 모음 사전 >
키워드 : 완전탐색 (백트래킹)
using System;
using System.ComponentModel;
public class Solution
{
int answer = 0, count = 0;
bool found = false; // 찾으면 중단
char[] vowels = { 'A', 'E', 'I', 'O', 'U' };
public int solution(string word)
{
DFS("", word);
return answer;
}
void DFS(string current, string target)
{
if (found) return; // 찾으면 더 이상 탐색 X
if (current == target)
{
found = true;
answer = count;
return;
}
if (current.Length == 5) return; // 최대 5글자까지만 가능
foreach (char c in vowels)
{
count++; // 단어 생성 카운트
DFS(current + c, target);
}
}
}
일반적인 완전 탐색(브루트포스) 형태로도 풀수 있지만 백 트래킹을 이용하면 더욱 쉽게 풀 수 있습니다.
백트래킹(Backtracking)이란?
백트래킹은 모든 경우의 수를 탐색하면서, 불가능한 경로는 즉시 되돌아가서 탐색하지 않는 법
즉, "가능성이 없는 경우는 더 이상 탐색하지 않고 되돌아간다(Pruning)"는 점이 핵심
또 기존에 백트래킹에 대해서 잘못알고 있는 사실이 있었는데,
기존에는
visited[i] = true;
if (route == "")
{
CheckTicket(list[i].Item2, count + 1, visited, route + list[i].Item1);
}
else
{
CheckTicket(list[i].Item2, count + 1, visited, route + "," + list[i].Item1);
}
visited[i] = false;와 같이, 특정 요소를 true로 하고, 이를 매개로 재귀함수를 돌린 후 다시 false 로 바꾸는 일련의 형태를 지녀야 백트래킹인 것으로 인식하고 있었는데 이게 아니라
if (found) return; // 찾으면 더 이상 탐색 X와 같이 불필요한 탐색을 즉시 종료하는 것이라면 백트래킹에 해당한다는 사실을 확인하게 되었습니다.
- 추가적으로, 백트래킹은 순서없이, 중복없이 의 조건을 가진 "조합" 문제를 풀 때 사용하기 아주 좋습니다. 모든 조건을 비교해 봐야할때 위와 같이 조합의 조건이라면 백트래킹을 사용하여야 합니다.
< CS 공부 >
( 객체 지향 프로그래밍 )
C# 에서의 특징으로 절차지향 언어인 C언어와는 차이점이 존재합니다.
객체 지향의 가장 큰 특징은 클래스를 이용해 함수(처리 부분), 변수(데이터 부분)를 묶어 하나의 객체(인스턴스)로 만들어 사용한다는 점입니다.
객체 지향의 4대 원칙 : 상속, 캡슐화, 추상화, 다형성
1. 상속
상속은 기존 클래스를 확장하거나 재사용하여 새로운 클래스를 생성하는것.
자식 클래스는 부모 클래스의 멤버를 상속받아 사용할 수 있고, 이러한 기능들을 확장하거나 수정하여새로운 클래스로 재정의 할 수 있다.
2. 캡슐화
연관 있는 변수와 메소드를 묶어주는 작업으로, 클래스의 필드 혹은 메소드들에 접근을 제한하는 것과도 관련이 있습니다. 이는 접근 지정자(public protected private)를 통해서 외부 접근을 제한하고, 객체 내에서만 접근 가능하도록 은닉합니다.
이를 통해서 얻는 효과는 아래와 같습니다.
- 데이터 무결성 보장 :
필드에 대한 직접적인 접근을 제한하고, 프로퍼티나 메서드 등을 통해서만 접근하도록 설정함으로써 잘못된 정보가 들어오는 것을 방지할 수 있다.- 유연한 유지보수 :
내부 구현이 외부에 노출되지 않으므로 내부 코드를 수정해도 외부에 영향이 미치지 않는다.- 객체의 상태 제어:
클래스 외부에서는 객체 상태를 임의로 변경할수 없기 때문에 객체 상태를 일관되게 유지 할 수 있다.
3. 추상화
객체에서 공통된 부분을 추출하는것을 의미한다. 즉 특정 기능을 구현할때 그 기능에 필요한 변수오 함수들을 추출하되, 공통 되는 부분은 재사용 할 수 있도록 하는것입니다.
위와 같은 두개의 클래스는 하나의 단일 클래스 Animal로 묶을 수 있고,
이를 이용해 반복되는 코드를 줄이고 재사용성을 높을 수 있습니다.
4. 다형성
같은 종류의 클래스가 하나의 메시지에 대해서 서로 다른 행동을 할 수있는것을 말합니다.
앞선 예시의 Say() 함수를 보면 Cat, Dog는 Animal 에서 같은 class를 가지지만 서로 다른 기능을 발현합니다. 이렇든 다형성을 통해 변경이 필요한 부분을 변경하여 사용할 수 있습니다.
다형성에 가장 연관 깊은 두 키워드는 Override 와 Overroad 입니다.
Overroad 는 앞서 살펴 보았듯, 하나의 함수 이름을 가지고 여러 매개변수에 대응할 수 있도록 재사용하는 것입니다.
Override는 재정의를 의미하며, 부모 클래스에서 선언된 함수들을 자식 객체에서 재정의하여 수정된 혹은 추가된 기능으로 사용 할 수 있습니다.
지금까지 살펴본것이 객체지향 프로그래밍의 특징 4가지 였다면 아래는 5가지 설계 원칙입니다. 이를 약자로 SOLID 원칙이라고 말합니다.
S - 단일 책임 원칙(Single Responsibility Principle)
클래스는 단 하나의 목적을 가지며, 클래스를 변경하는 이유도 하나 여야한다.
-> 이렇게 되면 변경할 때의 수정 대상이 명확해집니다.
O - 개방 폐쇠의 원칙(Open-Closed Principle)
확장에는 열려있고, 변경에는 닫혀있어야 한다.
-> 확장에 열려있다는 것은 요구사항이 변경될때 새로운 동작을 추가하는 것으로 기능을 확장할 수 있다는 것입니다.
-> 수정에 닫혀있다는 말은 기존 코드를 수정하지 않고 동작을 추가하거나 변경할 수 있는 것을 말합니다.
L - 리스코프 치환 원칙(Liskov Substitution Principle)
서브 클래스가 부모 클래스의 기능을 대체할 수 있도록 보장하는 원칙
-> 즉, 부모 클래스와 상호작용 할 때 자식 클래스(서브 클래스)를 넣어도 동작해야 한다는 것을 의미합니다. 이를 통해 유연하고 안정적인 상속 구조를 만들 수 있습니다. 이는 호환성 보장(부모 클래스의 기능을 변경x, 약화X) 일관성 유지(부모 클래스의 기대 동작 변경X) 를 의미합니다.
-> 리스코프 치환원칙 준수 방법
1. 서브 클래스는 기반 클래스의 기능을 유지하면서 새로운 기능을 추가하거나 확장해야 합니다.
2. 서브 클래스는 기반 클래스의 메서드와 속성이 기대하는 입,출력 을 변경하지 말아야 합니다,
3. 기반 클래스의 코드가 서브 클래스를 대처 할 때 문제없이 동작해야합니다.
I - 인터페이스 분리 원칙(Interface Segregation Principle)
객체는 이용하지 않는 매서드에 의존하지 않도록 인터페이스를 분리해야 한다.
객체가 높은 응집도의 낮은 단위로 설계되어 있어도, 목적과 기능이 각기 다른 클라이언트가 있다면 인터페이스를 분리시켜줘야 합니다.
-> 인터 페이스는 작게 유지 : 하나의 인터페이스에 많은 매서드를 정의하게 되면 이를 구현하는 클래스들은 자신이 사용하지 않는 메서드 또한 구현해야합니다.
-> 다중 인터페이스 : 인터페이슬 작은 단위로 분리하면 클래스는 여러 개의 인터페이스를 동시에 구현할 수 잇습니다.
이를 사용하면 클래스간 결합도가 감소해 불필요한 의존성을 제거하고, 시스템을 확장하거나 수정할때 유연하게 대처 할 수 있으며, 유지 보수가 쉬워집니다.
D - 의존관계 역전 원칙(Dependency Inversion Principle)
어떤 클래스를 참조해서 사용해야 한다면, 그 클래스를 직접 참조하는 것이 아니라 대상의 상위 요소인 인터페이스나 추상 클래스를 참조해야 한다.
---> 의존 관계를 맺을 때는 변화하기 쉬운 것 보다는 어려운것에 의존해야 합니다. 이는 인터페이스는 한번 설계되면 잘 변하지 않기 때문에 이에 의존하라는 내용입니다. 결과적으로 이는 클래스간의 결합도를 낮추어 유지 보수에 도움을 줍니다.
위와 같이 꽤나 긴 내용으로 4가지 특징과 5가지 설계 원칙에 대해서 설명을 찾아 보았습니다. 이는 단순히 원론 적인 이야기에서 벗어나, 실제로 프로젝트를 경험해 본 사람이라면 정말로 중요한 부분이라는 것을 알 수 있습니다.
따라서 개발 할 때에 위의 원칙을 지키면 좀 더 수월하게 작업을 진행해 나갈 수 있습니다.
- 부모 클래스의 메서드와 같은 이름, 매개변수를 가져야 한다.
