[백준 23083번] 파이썬 - 꿀벌 승연이

 

http://www.acmicpc.net/problem/23083

23083번: 꿀벌 승연이

 

# 조건

• 승연이가 사는 벌집은 조금 특이한 구조로 되어있다.
• 벌집은 N행 M열의 격자로 이루어져 있고, 각 칸은 정육각형 모양
• 같은 행에 위치한 두 칸을 비교했을 때, 짝수번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 위치

 

• 두 육각형 칸이 하나의 변을 공유하고 있다면 서로 인접하다.
• 벌집 내에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동가능하다.
• 또 벌집에는 구멍 칸이 있을 수 있는데 구멍칸으로는 이동 불가하다.
• 1행 1열에서 N행 M열 칸까지 이동하는 경로의 개수를 구하여라.

 

# 접근 방법 및 Solution

• 시간초과 - bfs 이용
  • BFS를 이용하여 deque에 추가되는 횟수를 기록해준다. deque에 추가되는 횟수 = 가능한 경로
  • 이 때 홀수 열의 칸과 짝수열의 칸의 오른쪽 좌표가 다르다.
  • 홀수 열
    • 아래 -> 행 +1
    • 오른쪽 위 -> 행 -1, 열 + 1
    • 오른쪽 아래 -> 열+1
    • 탐색해주면 된다.
  • 짝수 열
    • 아래 -> 행 + 1
    • 오른쪽 위 -> 열+1
    • 오른쪽 아래 -> 행+1, 열 + 1
• dp 이용
  • 시작점을 1로하여 홀수열과 짝수열에 올 수 있는 칸의 인덱스의 값을 더해준다.
  • 왼쪽 위, 왼쪽 아래, 바로 위
  • 짝수 열의 경우
    • 왼쪽 아래가 집 밖인 경우가 있어 시작할 때, 1행을 추가해주거나
    • 더할 때 조건을 달아주면 된다.
    • 시간 차이는 많이 x
  • 즉, (2,2) 의 칸은 (2,1) + (1,2) + (3,1)이 되어 4가 된다.
  • 이 때, 같은 열부터 채워주어야 올바른 덧셈이 이루어진다.

 

시간초과 - bfs

• 방문하지 않는 조건이 벌집 밖 또는 구멍 칸이 아닌경우 밖에 없어 바로 시간초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
N, M = map(int, input().split())  
K = int(input())  
  
bee_house = [[0]*(M+1) for _ in range(N+1)]  
for _ in range(K):  
    a, b = map(int, input().split())  
    # 구멍칸 기록  
    bee_house[a][b] = -1  
  
# bfs 돌려주기  
q = deque()  
# 1,1 시작  
q.append((1,1))  
  
# 홀수 탐색 방향 - 아래, 오른쪽 위, 오른쪽 아래  
odd_di, odd_dj = [1,-1,0], [0, 1, 1]  
# 짝수 - 아래, 오른쪽 위, 오른쪽 아래  
even_di, even_dj = [1,0,1], [0,1,1]  
while q:  
    sti, stj = q.popleft()  
    bee_house[sti][stj] += 1  
    # 홀수 열 탐색  
    if stj % 2:  
        for i in range(3):  
            ni, nj = sti+odd_di[i], stj+odd_dj[i]  
            if 1<=ni<=N and 1<=nj<=M and bee_house[ni][nj] != -1:  
                q.append((ni,nj))  
    # 짝수 열 탐색  
    elif not stj % 2:  
        for i in range(3):  
            ni, nj = sti+even_di[i], stj+even_dj[i]  
            if 1<=ni<=N and 1<=nj<=M and bee_house[ni][nj] != -1:  
                q.append((ni,nj))  
  
print(bee_house)

 

시간초과 2 - dp 이용

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
K = int(input())
mod = 10**9+7
bee_house = [[0]*(M+1) for _ in range(N+1)]
hole = []
for _ in range(K):
    a, b = map(int, input().split())
    # 구멍칸 넣어주기
    hole.append((a,b))


bee_house[1][1] = 1

# 1행, 1열은 채웠으므로
# 2행 2열부터 시작
# 이 때 열부터가 아닌, 행부터 채워주어야 한다.
for j in range(1,M+1):
    for i in range(1,N+1):
        if i == 1 and j == 1:
            continue
        # 구멍칸 통과
        if (i,j) in hole:
            continue
        # 짝수 열 기록
        if not j % 2:
            # 위는 체크 x 왼쪽 위도 체크 x 왼쪽 아래만 체크해주면 된다.
            # 왼쪽 아래가 범위 밖이라면, 왼쪽 위와 바로 위만 더해준다.
            if i+1 < N+1:
                bee_house[i][j] = (bee_house[i-1][j] + bee_house[i][j-1] + bee_house[i+1][j-1]) % mod
            else:
                bee_house[i][j] = (bee_house[i - 1][j] + bee_house[i][j - 1]) % mod

        # 홀수 열 기록
        else:
            # 홀수 열의 경우 덧셈해주는 칸이 모두 범위 내부임
            bee_house[i][j] = (bee_house[i-1][j] + bee_house[i][j-1] + bee_house[i-1][j-1]) % mod
print(bee_house[N][M])

 

# 통과 코드

• 구멍 칸의 수가 생각보다 크다.
• 따라서, 리스트로 append 하는 시간 + 살피는 시간이 시간초과의 원인
• set()과 add 메서드를 이용하여 구멍 칸을 기록해주었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
N, M = map(int, input().split())  
K = int(input())  
mod = 10**9+7  
# N번 행까지 사용해야되므로 덧셈시 조건을 줄이기 위해 한줄 더 생성  
bee_house = [[0]*(M+1) for _ in range(N+2)]  
# 시작점도 구멍으로 쳐주어서 0으로 초기화 안되게 하기  
hole = {(1,1)}  
for _ in range(K):  
    a, b = map(int, input().split())  
    # 구멍칸 넣어주기  
    hole.add((a,b))  
  
  
bee_house[1][1] = 1  
  
# 1행, 1열은 채웠으므로  
# 2행 2열부터 시작  
# 이 때 열부터가 아닌, 행부터 채워주어야 한다.  
for j in range(1,M+1):  
    for i in range(1,N+1):  
  
        # 구멍칸 통과  
        if (i,j) in hole:  
            continue  
        # 짝수 열 기록  
        elif not j % 2:  
            # 왼쪽 아래 조건 없애기 위해서 1행 더 추가해줌  
            bee_house[i][j] = (bee_house[i-1][j] + bee_house[i][j-1] + bee_house[i+1][j-1]) % mod  
        # 홀수 열 기록  
        else:  
            # 홀수 열의 경우 덧셈해주는 칸이 모두 범위 내부임  
            bee_house[i][j] = (bee_house[i-1][j] + bee_house[i][j-1] + bee_house[i-1][j-1]) % mod  
print(bee_house[N][M])

• 칸을 채워줄 때 바로 % mod 해주는 것과
• 마지막 답에만 % mod 해주는 것은 메모리와 시간차이가 크게 나는 것을 볼 수 있다.

 

 

위에 꺼는 답에만 % mod
아래는 더하는 과정에서 바로 % mod