본문 바로가기
[Algorithm] 백준 13787 Infinity Maze https://www.acmicpc.net/problem/13787 백준에서 문제 찾아보다가 이름이 맘에 드는 문제를 발견했습니다. 재작년에 출시한 게임 iMaze와 같은 이름! 너무 반가워서 바로 풀어보았습니다. 문제가 영어로 되어있어서 우리말로 풀어볼게요. 문제 후쿠오카 박사는 2D 미로에 간단한 로봇을 배치시켰습니다. 미로는 출구가 없어서 로봇이 밖으로 나갈 수 없습니다. 아래 그림처럼 H x W 격자 셀로 만들어졌고, 미로의 위, 오른쪽, 아래, 왼쪽은 각각 북(N), 동(E), 남(S), 서(W)쪽입니다. 각 셀은 벽(#)이거나 빈 공간(.)이고, 좌표 (i, j)에 대해 i는 남쪽으로 갈수록 커지고, j는 동쪽으로 갈수록 커져서, 가장 왼쪽 위부터 (1, 1), 가장 오른쪽 아래는 (H, W).. 2024. 2. 15.
[Algorithm] 백준 17114 하이퍼토마토 - 구데기같지 않은 풀이 (C++) https://www.acmicpc.net/problem/17114 구데기컵에 출제된 문제입니다. 구데기같이 11중 반복문과 BFS를 통해서 풀 수 있습니다. (물론 그게 아주 정상적인 방법입니다.) 하지만 차원 확장에 대해 조금 더 생각해보면 규칙을 발견할 수 있고, 11차원 뿐만 아니라 자연수 n에 대해 일반적으로 답을 낼 수 있습니다. 코드도 아주 짧아져서 숏코딩에 도전할 수도 있죠. 이 글에서는 제가 며칠 동안 삽질하면서 발견한 꽤 아름다운(?) 풀이를 설명하려 합니다. 관련 지식은 BFS만 알고 계시면 됩니다만, 꽤 인내심이 필요할 것 같습니다. 제가 부족한 탓에 쉽게 설명을 못하겠더라구요. 1. 토마토 배열을 일차원으로 표현 2차원(평면)은 1차원(선)을 모아놓은 것이고, 3차원은 2차원을 모.. 2022. 6. 14.

티스토리툴바