[S2] 백준 26071번 오락실에 간 총총이 C++ 애드혹

리뷰

 

https://www.acmicpc.net/problem/26071

한 1년만에 풀어본 애드혹 문제인데, 방향성은 잘 잡았으나 특정 상황에 대한 분기처리 누락으로 3번이나 틀렸다. ㅠㅠ

 

 

전역 변수

• n : 게임의 화면 크기를 저장할 변수

 

함수

없음

 

 

문제풀이

• n값을 입력 받고, minR, minC를 n, maxR, maxC를 -1로 초기화한다.
• n*n크기의 게임 화면을 입력 받고, minR, maxR, minC, maxC를 곰곰이의 좌표 값으로 최신화한다.
• 변수 V를 minR과 maxR이 같다면 0, 아니라면 maxR, (n-1)-minR 중 작은 값으로 저장한다.
• 변수 H를 minC과 maxC이 같다면 0, 아니라면 maxC, (n-1)-minC 중 작은 값으로 저장한다.
• V+H를 출력한다.

 

트러블 슈팅

1. 곰곰이를 모두 코너로 모는 것이 최적해로 생각하여 구현하여 WA를 받았다.
2. 곰곰이가 모두 같은 행 혹은 같은 열에 존재할 경우에 대한 분기 처리를 수행하였다.
3. 곰곰이가 한마리 밖에 없을때의 분기처리를 해주지 않아 WA를 받았다.
4. minR, maxR, minC, maxC를 기반으로 모든 분기를 처리해 주어 AC를 받았다.

 

참고 사항

1. 이동을 직접 구현하기엔 최대 1500*1500크기의 데이터 복사가 필요하므로 완전 탐색은 안된다고 생각했다.
2. 처음엔 R, C를 담을 set두개를 통해 begin(), rbegin()을 통한 해법을 구현하고자 하였다.
3. 하지만 변수 4개로 메모리와 시간을 더 효율적으로 사용하여 구현할 수 있는 풀이가 존재했다.
4. 곰곰이가 모두 같은 행 혹은 같은 열에 있거나, 곰곰이가 한마리 밖에 없을때의 분기처리만 신경써주면 된다.

 

정답 코드

#include<iostream>
using namespace std;

int n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	int minR = n, maxR = -1, minC = n, maxC = -1;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;

		for (int j = 0; j < n; ++j) {
			if (s[j] == 'G') {
				minR = min(minR, i);
				maxR = max(maxR, i);
				minC = min(minC, j);
				maxC = max(maxC, j);
			}
		}
	}

	int V = (minR == maxR) ? 0 : min(maxR, (n - 1) - minR);
	int H = (minC == maxC) ? 0 : min(maxC, (n - 1) - minC);
	//cout << V << " " << H << "\n";
	cout << (V + H);
}