B2873

개요

백준 문제 2873번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ?분
https://www.acmicpc.net/problem/2873

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

코드

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

풀이

일단 당연히 모든 점을 순회할 수 있으면 가장 높은 점수가 나온다.
그래서 모든 점을 순회가능한 경우에는 모두 순회하는데
문제는 가로와 세로가 짝수인 경우에는 모두 순회할 수 없고 딱 한점을 피해서 가면 순회할 수 있어
그 딱 한점을 피해서 가야한다.
한 점을 피하는 건 우선 전체 점을 둘러보면서 가장 작은 점을 찾는다.
그 뒤가 어려운데, 그 점의 좌표를 기준으로 최대한 많은 점을 순회하며 바로 왼쪽에 도달한 다음,
왼쪽 아래 대각선으로 이동 오른쪽으로 이동 이후 마지막까지 순회하면 완성

배울 점, 메모

나는 이 문제를 자력으로 풀진 못했다.
모든 점을 순회하면 되는 두 경우는 생각했으나
가로 세로가 짝수인 경우에는 안된다는 것을 찾지 못했고 검색을 통해
알았지만, 실제로 구현할려고 생각하면 좀 복잡해서 이해하기도 힘들었다.
이 문제를 풀면서 부족했던 능력은

1. 문제를 읽고 케이스별을 놓침(문제에 대한 시간을 많이 쓰지 않음) - 여러 케이스를 직접 만들어서 하나씩 해야함
2. 구현력 부족 - 많은 시간을 들여서 노력하는 수 밖에 없음