프로그래머스 문제
https://school.programmers.co.kr/learn/courses/30/lessons/169199
풀이 후기
1. 그거
포켓몬 그거. 배열로 게임 비슷하게 만들기 + 군대에서 엑셀로 한 번 만들어봐서 구현 자체는 걱정 안 됐지만, 문제를 어떻게 해결해야 할까 고민이 좀 있었다. BFS나 DFS를 쓰라는 문제인 게 딱 봐도 보이긴 하지만 구현해본 기억이 왜인지 없음...
그리고 포켓몬으로 이 퍼즐 풀 때는 도착 지점부터 가는 게 찾기 편해서 코드도 그렇게 짜봤다. 근데 위 돌 때문에 도착한 경로라도 옆으로 시작하는 문제가 있어서 얌전히 캐릭터부터 시작하게 바꿈. 아니면 시작지점 + 돌 위치를 고려해서 시작 로그만 미리 깔아두는 것도 괜찮을 듯.
2. 움직임에 관하여
public (int, int) MoveUp(int x, int y)
{
while (map[x, y] != 'D')
{
x--;
}
return (x + 1, y);
}나는 움직이는 방법에 while을 때려 박아서 체크하는 방식을 사용했다. 짜는 도중에 갑자기 ＇장애물과 캐릭터 좌표만 비교해서 도착할 위치를 체크하면 어떨까?＇가 있었는데 ＇while은 많아도 100번이면 끝나는데 굳이 번거롭게?＇ 라는 생각이 떠올라서 빠르게 기각됨.
3. 움직임 로그
초기에 생각한 방식은
- 도착한 위치에서 자신이 이 자리를 몇 번의 움직임으로 도착했는지 로그를 저장한다.
- 도착한 곳에 이미 로그가 있다면 몇 번 움직였는지 비교해서 적은 쪽으로 바꿔치기한다.
- 모든 로그 기준으로 상하 좌우로 이동한다.
4. 시간 초과
하지만 또 시간 초과가 발생한다. 아마도 범인은 로그가 중복으로 실행된다는 점. 이 부분을 수정하기는 시행착오가 좀 있었다. 이것저것 곰곰이 생각해보니 ＇초기에 기록한 로그의 카운트가 후반에 기록한 로그보다 카운트가 낮을 수 있나?＇ 당연히 그런 일은 없다. 아마도 BFS, DFS, 재귀를 좀 생각하다 보니까 순차적으로 기록되지 않을 수 있다는 생각 때문에 그렇게 구현한 것 같았다. 그래서 로그에서 active flag, count, prev log 같은 쓸모없는 정보들을 다 제거하니 남은 건 좌표 정보뿐...
5. 또 시간 초과
그런데 또 시간 초과가 발생한다. 특정 알고리즘 안 쓰면 포기하라는 소리인지 화가 좀 났지만, 눈에 띄는 부분부터 변경하기로 한다. 도착 좌표를 리스트에서 Find로 탐색하는 과정을 리스트에도 저장하고 배열에도 또 저장하는 방식으로 바꿔서 Find 함수를 제거했다. 생각해보니 로그는 리스트에서 한 번 꺼내서 사용하고 다시는 안 써서 Queue로 변경도 했다.
6. 또또 시간 초과
대부분의 테스트 케이스는 1~2초 사이로 줄었는데 또 몇몇 케이스가 문제였다. 드디어 알고리즘의 시간 복잡도가 문제가 아니라 골인 지점까지 갈 수 없는 문제임을 깨달았다. 나는 대충 도착할 수 없는 조건을 '골인 지점 주변에 돌 없음'으로 했는데,
이런 케이스도 존재하겠구나 생각이 들었다. 설마 진짜인가 싶어서 대충 10000번 넘으면 -1을 리턴하게 바꿨더니 통과...
while (game.ProcessMove())
{
count++;
if (count > 10000)
{
return -1;
}
}허무하긴 했지만, 최적화에 대해 배웠으니 된 게 아닐까...
7. 진짜 해답
해답이 없는 조건은 간단하게 추가했다. 해당 칸에 이미 로그가 있으면 로그를 추가 안 하고 버리기로 했는데, 해답이 없는 케이스는 도착할 수 없이 같은 자리를 반복하기 때문에 사용할 로그가 없겠구나~ 같은 느낌.
아무튼 오늘도 성공.
8. 코드
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
class MoveLog
{
public (int, int) pos;
public MoveLog(int x, int y)
{
pos = (x, y);
}
}
class Game
{
private char[,] map;
private Queue<MoveLog> moveLogsList;
private MoveLog[,] moveLogsArray;
private (int, int) goalPos;
private int mapLenX;
private int mapLenY;
private int count;
public Game(string[] board)
{
count = 0;
mapLenX = board.GetLength(0) + 2;
mapLenY = board[0].Length + 2;
map = new char[mapLenX, mapLenY];
moveLogsList = new Queue<MoveLog>();
moveLogsArray = new MoveLog[mapLenX, mapLenY];
for (var x = 0; x < mapLenX; x++)
{
for (int y = 0; y < mapLenY; y++)
{
if (x == 0 || y == 0 || x == mapLenX - 1 || y == mapLenY - 1)
{
map[x, y] = 'D';
continue;
}
var value = board[x - 1][y - 1];
if (value == 'R')
{
map[x, y] = '.';
moveLogsList.Enqueue(new MoveLog(x, y));
}
else if (value == 'G')
{
goalPos = (x, y);
map[x, y] = '.';
}
else
{
map[x, y] = value;
}
}
}
}
public bool IsPossible()
{
var x = goalPos.Item1;
var y = goalPos.Item2;
var condition1 = map[x + 1, y] == 'D';
var condition2 = map[x - 1, y] == 'D';
var condition3 = map[x, y - 1] == 'D';
var condition4 = map[x, y + 1] == 'D';
return condition1 || condition2 || condition3 || condition4;
}
public void CheckMoveCount((int, int) movePos)
{
var moveLog = moveLogsArray[movePos.Item1, movePos.Item2];
if (moveLog == null)
{
var newLog = new MoveLog(movePos.Item1, movePos.Item2);
moveLogsList.Enqueue(newLog);
moveLogsArray[movePos.Item1, movePos.Item2] = newLog;
}
}
public int ProcessMove()
{
var logsCount = moveLogsList.Count;
for (int i = 0; i < logsCount; i++)
{
var log = moveLogsList.Dequeue();
var x = log.pos.Item1;
var y = log.pos.Item2;
CheckMoveCount(MoveUp(x, y));
CheckMoveCount(MoveDown(x, y));
CheckMoveCount(MoveLeft(x, y));
CheckMoveCount(MoveRight(x, y));
}
count++;
if (logsCount == 0)
{
return -1;
}
var findChar = moveLogsArray[goalPos.Item1, goalPos.Item2];
if (findChar != null)
{
return count;
}
return 0;
}
public (int, int) MoveUp(int x, int y)
{
while (map[x, y] != 'D')
{
x--;
}
return (x + 1, y);
}
public (int, int) MoveDown(int x, int y)
{
while (map[x, y] != 'D')
{
x++;
}
return (x - 1, y);
}
public (int, int) MoveLeft(int x, int y)
{
while (map[x, y] != 'D')
{
y--;
}
return (x, y + 1);
}
public (int, int) MoveRight(int x, int y)
{
while (map[x, y] != 'D')
{
y++;
}
return (x, y - 1);
}
}
public int solution(string[] board) {
var game = new Game(board);
if (!game.IsPossible())
{
return -1;
}
while (true)
{
var count = game.ProcessMove();
if (count != 0)
{
return count;
}
}
}
public static void Main(string[] args)
{
new Solution().solution(new string[]{".D.R", "....", ".G..", "...D"});
}
}
