프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제요약!
최대 4 * 4의 퍼즐판에서 파란 수레와 빨간 수레를 한턴에 한번 씩 움직여 각각의 도착지점으로 보낼때의 최소 턴수를 구하는 문제!
조건으로는
1. 각각의 수레, 자신이 방문했던 칸으로는 다시 움직일수 없다
2. 같은 칸으로 동시에 움직일 수 없다.
3. 서로 자리를 바꾸며 움직일 수 없다.
4. 도착한 수레는 더이상 움직이지 않는다.
조건이 상당히 까다로운 문제였습니다....
그만큼 예외사항이 많아 잘 처리해주지 않으면 시간이 많이 걸리는 문제였습니다...
그래도 시작!
처음 드는 생각은 DFS탐색방법이였습니다
수레하나로 다음 문제를 풀었다면, 무조건 dfs방법을 통해 빠르게 풀어나갔을텐데!
기존 코드베이스에서 수레를 하나 더 추가하는 방법을 찾아 수정해야할 것 같습니다.
바로 코드 시작!
기존 dfs코드에서 선언해주었던 기본 변수들을 선언해 줍시다.
방향, 방문,턴 수 , 퍼즐판의 크기를 선언해줍시다.
그리고 각각의 수레의 시작위치와 도착지점, 도착여부를 저장할 List를 하나만 더 선언해줍시다.
int size_y;
int size_x;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1,0, 0 };
int visit_R[5][5]; // 방문
int visit_B[5][5]; // 방문
vector<vector<int>> List(5, vector<int>()); // 정보저장 List[4] 성공 여부
int answer = 987654321;// 이동 턴수
기본 변수 선언 뒤 solution함수를 시작하며 변수들을 초기화 해줍시다.
int solution(vector<vector<int>> maze) { // 0 빈칸 / 1 빨간 시작 / 2 파랑 시작/ 3 빨강 도착 / 4 파랑 도착 / 5 벽
size_y = maze.size();
size_x = maze[0].size();
for (int i = 0; i < size_y; i++) {
for (int j = 0; j < size_x; j++) {
if (maze[i][j] == 5) { // 벽
visit_R[i][j] = 1;
visit_B[i][j] = 1;
}
else if (maze[i][j] == 1) { // 빨강 시작
List[0] = { i,j };
visit_R[i][j] = 1;
}
else if (maze[i][j] == 2) {
List[1] = { i,j };
visit_B[i][j] = 1;
}
else if (maze[i][j] == 3) { // 빨강 도착
List[2] = { i,j };
}
else if (maze[i][j] == 4) {
List[3] = { i,j };
}
}
}
List[4] = { 0,0 };
List [4][0] 은 빨간 수레가 도착했는지
List [4][1] 은 파란 수레가 도착했는지를 저장해줄 것입니다.
그런다음 탐색을 시작해줍시다.
구성하다 보니 생각보다 코드가길고 복잡해졌는데.....
나누어보면
처음은 아래처럼 도착을 확인하는 부분과 최소턴수를 통해 걸러주는 부분을 구성하고
void dfs(int count, vector<int> red, vector<int>blue) { // 이동수, 빨 파 위치
if (List[4][0]*List[4][1]==1) {// 도착 확인
answer = min(count, answer);
return; // 탐색 끝!
}
if (answer <= count) {
return; // 최소치보다 안됨 탐색 중지
}
....
그다음 두 수레는 이중 for문을 통해 구성해주었습니다.
먼저 빨간 수레부터 탐색을 통해 이동 시켜 주고,
....
for (int i = 0; i < 4; i++) {
int tempR_y = red[0] + dy[i];
int tempR_x = red[1] + dx[i];
int tempB_y = 0;
int tempB_x = 0;
if (red == List[2]) {
List[4][0] = 1;
}
if (List[4][0] != 1) { // 아직 도착 x
if (tempR_y < 0 || tempR_y >= size_y || tempR_x < 0 || tempR_x >= size_x) {
continue;
}
else if(visit_R[tempR_y][tempR_x]==1) {
continue;
}
}
else {
tempR_y = List[2][0];
tempR_x = List[2][1];
}
visit_R[tempR_y][tempR_x] = 1;
....
파란수레도 내부 for문을 통해 이동 시켜 주었습니다.
for (int j = 0; j < 4; j++) {
if (blue == List[3]) {
List[4][1] = 1;
}
tempB_y = blue[0] + dy[j];
tempB_x = blue[1] + dx[j];
if (List[4][1] != 1) { // 아직 도착 x
if (tempB_y < 0 || tempB_y >= size_y || tempB_x < 0 || tempB_x >= size_x) {
continue;
}
else if (visit_B[tempB_y][tempB_x] == 1) {
continue;
}
}
else {
tempB_y = List[3][0];
tempB_x = List[3][1];
}
if (tempR_y == blue[0] && tempR_x == blue[1]&& tempB_y == red[0] && tempB_x == red[1]) {
continue; // 두 수레가 서로 위치를 바꾸며 이동하는 부분제외
}
if (tempR_y == tempB_y && tempR_x == tempB_x) {
continue; // 두수레가 같은 칸으로 이동하는 부분 제외
}
visit_B[tempB_y][tempB_x] = 1;
dfs(count + 1, { tempR_y, tempR_x }, { tempB_y, tempB_x });
visit_B[tempB_y][tempB_x] = 0;
List[4][1] = 0;
}
visit_R[tempR_y][tempR_x] = 0;
List[4][0] = 0;
}
return;
}
내부 구성은 둘다 비슷한데
여기서 한가지 확인해야 할 부분은
1. 현재 수레가 도착했다면 이동 x
2. 두 수레가 겹쳐서 이동하는 경우를 제외
3. 두 수레가 충돌하는 경우를 제외
그다음 visit(방문)과 List[4](도착여부)를 최신화 해주며 재귀적으로 탐색시키면 끝!
문제자체는 단순 dfs를 통한 탐색으로 풀어낼 수 있는 쉬운 편의 문제였습니다.
하지만 예외사항에 대해 처리하고 방문처리를 따로 해주어야한다는 부분을 잘 설계해야 풀리는 문제였던것 같습니다!
ALL
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int size_y;
int size_x;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1,0, 0 };
int visit_R[5][5]; // 방문
int visit_B[5][5]; // 방문
vector<vector<int>> List(5, vector<int>()); // 정보저장 List[4] 성공 여부
int answer = 987654321;// 이동 턴수
void dfs(int count, vector<int> red, vector<int>blue) { // 이동수, 빨 파 위치
if (List[4][0]*List[4][1]==1) {// 도착 확인
answer = min(count, answer);
return; // 탐색 끝!
}
if (answer <= count) {
return; // 최소치보다 안됨 탐색 중지
}
for (int i = 0; i < 4; i++) {
int tempR_y = red[0] + dy[i];
int tempR_x = red[1] + dx[i];
int tempB_y = 0;
int tempB_x = 0;
if (red == List[2]) {
List[4][0] = 1;
}
if (List[4][0] != 1) { // 아직 도착 x
if (tempR_y < 0 || tempR_y >= size_y || tempR_x < 0 || tempR_x >= size_x) {
continue;
}
else if(visit_R[tempR_y][tempR_x]==1) {
continue;
}
}
else {
tempR_y = List[2][0];
tempR_x = List[2][1];
}
visit_R[tempR_y][tempR_x] = 1;
for (int j = 0; j < 4; j++) {
if (blue == List[3]) {
List[4][1] = 1;
}
tempB_y = blue[0] + dy[j];
tempB_x = blue[1] + dx[j];
if (List[4][1] != 1) { // 아직 도착 x
if (tempB_y < 0 || tempB_y >= size_y || tempB_x < 0 || tempB_x >= size_x) {
continue;
}
else if (visit_B[tempB_y][tempB_x] == 1) {
continue;
}
}
else {
tempB_y = List[3][0];
tempB_x = List[3][1];
}
if (tempR_y == blue[0] && tempR_x == blue[1]&& tempB_y == red[0] && tempB_x == red[1]) {
continue;
}
if (tempR_y == tempB_y && tempR_x == tempB_x) {
continue;
}
visit_B[tempB_y][tempB_x] = 1;
dfs(count + 1, { tempR_y, tempR_x }, { tempB_y, tempB_x });
visit_B[tempB_y][tempB_x] = 0;
List[4][1] = 0;
}
visit_R[tempR_y][tempR_x] = 0;
List[4][0] = 0;
}
return;
}
int solution(vector<vector<int>> maze) { // 0 빈칸 / 1 빨간 시작 / 2 파랑 시작/ 3 빨강 도착 / 4 파랑 도착 / 5 벽
size_y = maze.size();
size_x = maze[0].size();
for (int i = 0; i < size_y; i++) {
for (int j = 0; j < size_x; j++) {
if (maze[i][j] == 5) { // 벽
visit_R[i][j] = 1;
visit_B[i][j] = 1;
}
else if (maze[i][j] == 1) { // 빨강 시작
List[0] = { i,j };
visit_R[i][j] = 1;
}
else if (maze[i][j] == 2) {
List[1] = { i,j };
visit_B[i][j] = 1;
}
else if (maze[i][j] == 3) { // 빨강 도착
List[2] = { i,j };
}
else if (maze[i][j] == 4) {
List[3] = { i,j };
}
}
}
List[4] = { 0,0 };
dfs(0, List[0], List[1]);
if (answer == 987654321) {
answer = 0;
}
else {
answer -= 1;
}
return answer;
}
틀린점이 있다면 댓 달아주세요!
'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글
| 코딩테스트 -- 고고학 최고의 발견 - (프로그래머스 / C++) (0) | 2024.04.02 |
|---|---|
| 코딩테스트 -- 산 모양 타일링 - (프로그래머스 / C++) (0) | 2024.03.20 |
| 코딩테스트 -- 상담원 인원 - (프로그래머스 / C++) (0) | 2024.03.18 |
| 코딩테스트 -- n + 1 카드게임 - (프로그래머스 / C++) (1) | 2024.03.14 |
| 코딩테스트 -- [PCCP 기출문제] 2번 / 석유 시추 - (프로그래머스 / C++) (0) | 2024.03.13 |
댓글