Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Object Poling
- LayerMark
- 오브젝트 풀링
- C#
- Unity
- Animation State Machine
- 2D슈팅게임
- 플레이어 방향전환
- pccp 기출문제 3번
- pccp 기출문제 2번
- 충돌위험 찾기
- Scrooling
- raycasting
- Object Pooling
- pccp 기출문제 1번
- Back Tracking
- ASTAR
- Algorithm
- Ainimation Blending
- Blend Type
- CSharp #자료구조
- Hpbar
- 플레이어 이동
- 깊이 우선 탐색
- Lv2
- 너비 우선 탐색
- 프로그래머스
- heap tree
- 유니티
- Hp바
Archives
- Today
- Total
주녘공부일지
[프로그래머스 C#] Lv.3 / 2차원 동전 뒤집기 본문
https://school.programmers.co.kr/learn/courses/30/lessons/131703#
1. 정답코드 및 핵심 아이디어, 유의사항
주어진 조건에 따라 초기 상태에서 목표 상태로 변경하기 위한 최소 변경 횟수를 구하는 문제
- 만약 목표 상태로 변경할 수 없다면 -1을 리턴
같은 행에 대한 연산이나 열에 대한 연산은 두번 이상 이루어져도 의미가 없음
- 각 열과 행은 뒤집은 경우와 뒤집지 않은 경우로 나뉨
-> DFS 알고리즘을 이용해 모든 경우의 수를 구함 (완전탐색)
https://godgjwnsgur7.tistory.com/47
주석 참조
using System;
public class Solution
{
public int solution(int[,] beginning, int[,] target)
{
int answer = -1;
// 각 인덱스에 대해 beginning == target ? 1 : -1 이 들어간 배열
var intArrays = new int[target.GetLength(0), target.GetLength(1)];
for (int i = 0; i < target.GetLength(0); i++)
for (int j = 0; j < target.GetLength(1); j++)
intArrays[i, j] = (beginning[i, j] == target[i, j]) ? 1 : -1;
DFS(0, 0, intArrays, ref answer);
return answer;
}
public void DFS(int currNum, int count, int[,] intArrays, ref int answer)
{
int index = currNum;
// 모든 행과 열에 대한 연산을 마쳤다면
if (index == intArrays.GetLength(0) + intArrays.GetLength(1))
{
foreach (int num in intArrays)
if (num == -1)
return;
// 목표상태에 도달한 경우라면
if (answer == -1)
answer = count;
else
answer = Math.Min(answer, count);
return;
}
if (index >= intArrays.GetLength(0)) // 열 연산 (행 연산이 끝난 경우)
{
index -= intArrays.GetLength(0); // 인덱스 돌려놓기
// 열을 뒤집은 경우
for (int i = 0; i < intArrays.GetLength(0); i++)
intArrays[i, index] *= -1;
DFS(currNum + 1, count + 1, intArrays, ref answer);
for (int i = 0; i < intArrays.GetLength(0); i++)
intArrays[i, index] *= -1;
// 뒤집지 않은 경우
DFS(currNum + 1, count, intArrays, ref answer);
}
else // 행 연산
{
// 행을 뒤집은 경우
for (int i = 0; i < intArrays.GetLength(1); i++)
intArrays[index, i] *= -1;
DFS(currNum + 1, count + 1, intArrays, ref answer);
for (int i = 0; i < intArrays.GetLength(1); i++)
intArrays[index, i] *= -1;
// 뒤집지 않은 경우
DFS(currNum + 1, count, intArrays, ref answer);
}
}
}
'CodingTest > Programmers Lv.3' 카테고리의 다른 글
[프로그래머스 C#] Lv.3 숫자 게임 (0) | 2024.03.06 |
---|---|
[프로그래머스 C#] Lv.3 표 병합 (0) | 2024.02.29 |
[프로그래머스 C#] Lv.3 부대 복귀 (1) | 2024.02.24 |
[프로그래머스 C#] Lv.3 아이템 줍기 (0) | 2024.02.21 |
[프로그래머스 C#] Lv.3 등대 (0) | 2024.02.19 |