[코테] 백준 class 5 - 구현/시뮬레이션

[12100] 2048 (Easy)

[13460] 구슬 탈출 2

그동안 공부한 알고리즘들이 모두 헛수고가 되는 듯한 개빡센 구현/시뮬레이션 문제...

solved.ac 클래스5에 있으면서 삼성 SW 역량 테스트 기출 문제집에도 있던데, 이 두개만 풀어봐도 대충... 거기서 어떤 문제가 나오는지 알거같다.

그래프, BFS, 백트래킹은 그냥 거들뿐이고 "그래서 어떻게 구현하라는건데"라는 말이 절로 나온다. 🤬

그놈의 상하좌우상하좌우상하좌우상하좌우상하좌우우우우우우우👎👎👎

아무튼 푼 김에 정리나 해보려고 한다.

1. 백트래킹? BFS?

게임판, 그러니까 기본적으로 NxN 크기의 2차원배열을 기준으로 하는데, 이 게임판을 어떻게 가지고 다닐건지에 따라 달라진다.

아직 두 문제밖에 풀지 않았으므로 일반화할 수는 없겠지만 내 생각으로는 이렇게 나눌 수 있을 거 같다.

• 게임판의 상태가 계속 바뀌고 이를 다음 차례에 활용해야하는 경우
  => 백트래킹
  => ex. 2048 (Easy)
• 게임판의 상태는 그대로이고, 위에 말(?)의 위치만 바뀌는 경우
  => BFS
  => ex. 구슬 탈출 2

근데 상식적으로 게임판의 상태가 계속 바뀌는 문제는 BFS로 풀 수가 없다. 그 바뀐 상태의 게임판을 일일이 다 가지고 다니려면...? 메모리 터질듯

2. 상하좌우

모든 방향에 대해 일반화되는 규칙이 분명 있을테니 이걸 찾아야한다.

각 방향의 움직임은

# 상, 하, 좌, 우
dx = [0,1,0,-1]
dy = [1,0,-1,0]
for i in range(4):
	다음x = 현재x + dx[i]
	다음y = 현재y + dy[i]

이렇게 변수로 한번에 퉁쳐버릴 수 있게 (?)

💎 [백준 12100 : PYTHON] 2048 (Easy)
💎 [백준] 12100 2048(easy) (python 파이썬)

설명은 어려우므로 위 블로그 참고

3. 패딩값 넣기

위 문제에 해당하는 건 아니고

[9328] 열쇠

얘를 풀다가 써놔야지 했던 거다.

이런 길찾기 문제에서 가장자리를 고려해야한다면 상하좌우 가장자리에 패딩값을 넣어서 가장자리도 내부인 것처럼 사용하자.