[알고리즘] 백준 5913번: 준규와 사과 (C++), 배운 게 많은 문제

이 문제는 논리를 쉽게 떠올릴 수 있었지만 그 논리를 구현하는 데에 있어서 많은 고민을 했다. 

밭을 돌아다니는 게 한 사람이 아닌 두 사람이라 함수를 두 개 선언해야 할지 함수를 두 번 콜 해야 할지 혹은 함수 하나에 두 명을 돌아다니게 하는 방법이 있는지 고민을 하다가 모든 방법이 구현이 다 어렵게 느껴져서 논리를 찾아보았다.

 

논리를 보고서 그냥 말이 안 나왔다. 잠깐 멍 때렸던 거 같다. '왜 이런 생각을 못 했지'라는 말이 나왔다.

두 명을 돌아다니게 하는 것이 아니라 한 명이 모든 구역을 돌아다니게 하는 방법을 생각하면 되었었다.

문법도 알고리즘의 문제도 아닌 논리의 문제가 가끔 머리를 세게 친다.

점점 어려운 문제들을 풀어보면서 결국엔 다 알고리즘 문제가 아니라 논리의 문제 같다고 느껴진다.

 

---

생각지도 못 한 코드

이번 문제에서는 논리뿐만 아니라 코드의 측면에서도 많이 배웠다.

 

https://jaimemin.tistory.com/499

백준 5913번 준규와 사과

 

1. up, down, left, right 방향으로 움직여야 할 때, 4가지 방향 모두 움직이게 하는 방법을 어떻게 해야 하는지 까마득했었다.

> 원래는 기존의 방향이 막히면 다른 방향을 고려하는 코드만 짤 수 있었다. (+추가 내용 맨 밑에)

>> direction 구조체 타입을 선언하고 for를 4번 돌려 모든 경우의 수를 탐색할 수 있었다.

 

2. 나머지는 기존의 백트래킹 방식으로 방문한 곳을 방문하지 않게 하거나 범위를 벗어나지 않도록 조건을 달아주거나 백트래킹의 구조를 가지고 있었고 그게 보였다는 점에서 많이 배웠다.

 

#include <iostream>
#include <vector>
using namespace std;

int arr[6][6] = { 0, };
int answer = 0;

typedef struct {
	int y, x;
} direction;

direction dir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; // up, down, right, left

void sol(int row, int col, int cnt, int lastGoal) {
	if (row == 5 && col == 5) {
		if (lastGoal == cnt) {
			answer++;
		}
		return;
	}

	//cout << row << ' ' << col << '\n';

	for (int i = 0; i < 4; i++) {// row와 col을 사용하면 안 된다. 기존의 인자변수라 다른 백트래킹에 영향을 미친다.
		int nextY = row + dir[i].y;
		int nextX = col + dir[i].x;

		if (nextY >= 1 && nextY <= 5 && nextX >= 1 && nextX <= 5 && arr[nextY][nextX] == 0) {
			arr[nextY][nextX] = 1;
			sol(nextY, nextX, cnt + 1, lastGoal);
			arr[nextY][nextX] = 0;
		}
	}
}

int main() {
	int n;
	cin >> n;
	int max = 25 - n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	arr[1][1] = 1;
	sol(1, 1, 1, max);
	cout << answer;
	return 0;
}

 

그리고, 이건 개인적인 오류였지만 주석으로도 처리가 되어있는데 for문 안에서 기존의 row와 col에 방향 값들을 넣어주어서 오류가 계속 났었다. for문이 돌 때마다 선언을 새로 해주어야 한다. 그렇지 않으면 up방향으로 가는 값들을 더해주고 다음 for문에서 그 값의 그대로 다른 방향의 값들을 넣어주어서 논리적 오류가 발생하기 때문이다.

 

---

느낀 점

 

1. 방향 4가지를 typedef를 통해 선언해주었다는 점

2. for를 4번 돌며 모든 방향의 경우의 수를 따질 수 있었다는 점

 

새로운 코딩 영역을 넓힌 느낌이다.

---

틀렸던 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<pair<int, int>> ans1;
vector<pair<int, int>> ans2;
int cnt1 = 0;
int cnt2 = 0;

void sol1(vector<vector<int>>& arr, int row, int col, int cnt, int cntFull) {
	if (cnt == cntFull) {
		ans1.push_back(make_pair(row, col));
		return;
	}

	arr[row][col] = 1;

	if (row > 1 && arr[row - 1][col] == 0) { // up
		sol1(arr, row - 1, col, cnt + 1, cntFull);
	}
	else if (row < 5 && arr[row + 1][col] == 0) { // down
		sol1(arr, row + 1, col, cnt + 1, cntFull);
	}
	else if (col > 1 && arr[row][col - 1] == 0) { // left
		sol1(arr, row, col - 1, cnt + 1, cntFull);
	}
	else if (col < 5 && arr[row][col + 1] == 0) { // right
		sol1(arr, row, col + 1, cnt + 1, cntFull);
	}

	return;
}

void sol2(vector<vector<int>>& arr, int row, int col, int cnt, int cntFull) {
	if (cnt == cntFull) {
		ans1.push_back(make_pair(row, col));
		return;
	}

	arr[row][col] = 1;

	if (row > 1 && arr[row - 1][col] == 0) { // up
		sol2(arr, row - 1, col, cnt + 1, cntFull);
	}
	else if (row < 5 && arr[row + 1][col] == 0) { // down
		sol2(arr, row + 1, col, cnt + 1, cntFull);
	}
	else if (col > 1 && arr[row][col - 1] == 0) { // left
		sol2(arr, row, col - 1, cnt + 1, cntFull);
	}
	else if (col < 5 && arr[row][col + 1] == 0) { // right
		sol2(arr, row, col + 1, cnt + 1, cntFull);
	}

	return;
}

int main() {
	int n;
	cin >> n;
	int max = 24 - n;

	vector<vector<int>> arr(6, vector<int>(6, 0));

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}

	sol1(arr, 1, 1, 1, max / 2 + 1);

	for (int i = 0; i < ans1.size(); i++) {
		cout << ans1[i].first << ' ' << ans1[i].second << '\n';
	}
	
	sol2(arr, 5, 5, 1, max / 2 + 1);

	for (int i = 0; i < ans2.size(); i++) {
		cout << ans2[i].first << ' ' << ans2[i].second << '\n';
	}

	return 0;
}