[BaekJoon] 15558 점프 게임

🔦 문제 링크

✍️ 나의 풀이

---

• 기본적인 BFS 문제이다.
• 각각의 경우 ( +1, -1, jump + k ) 를 나눠 큐에 넣는다.
• 이 때 반드시 방문 체크를 해줘야 메모리가 초과되지 않는다.
• count가 하나씩 늘어난다는 것만 조심해주면 된다.

🛠 나의 코드

---

from collections import deque
n, k = map(int, input().split())
arr = [list(map(int, list(input()))) for _ in range(2)]
check = [[False]*n for _ in range(2)]
q = deque()
q.append((0, 0, 0))
while q:
    col, pos, count = q.popleft()
    if pos+1 > n-1 or pos+k > n-1:
        print(1)
        exit(0)
    if pos+1 > count and arr[col][pos+1] and not check[col][pos+1]:
        check[col][pos+1] = True
        q.append((col, pos+1, count+1))
    if pos-1 > count and arr[col][pos-1] and not check[col][pos-1]:
        check[col][pos-1] = True
        q.append((col, pos-1, count+1))
    if pos+k > count and arr[(col+1) % 2][pos+k] and not check[(col+1) % 2][pos+k]:
        check[(col+1) % 2][pos+k] = True
        q.append(((col+1) % 2, pos+k, count+1))
print(0)

✍️ 다른 사람 풀이

---

• 3가지 경우를 for문을 통해 깔끔히 정리했다.
• 또한 for문을 사용해 범위가 하나씩 줄어드는 것을 구현했다.

🛠 다른 사람 코드

---

def bfs():
    q = deque()
    q.append((0, 0))
    for i in range(n):
        for j in range(len(q)):
            x, y = q.popleft()
            for nx, ny in (x, y-1), (x, y+1), (not x, y+k):
                if ny >= n:
                    print(1)
                    return
                if ny > i and not check[nx][ny] and a[nx][ny] == '1':
                    q.append((nx, ny))
                    check[nx][ny] = True
    print(0)

📝 정리

---

• 방문 체크는 언제나 중요하다. (안해도 될 것 같아도 해야한다)
• count를 세는 대신 for문과 queue의 현재 길이를 통해서 구현도 가능하다.

🎈 참고

---

rebas님 블로그