Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 누적 합
- Python
- 그래프
- 트리
- 세그먼트 트리
- 슬라이딩 윈도우
- 13164
- 문자열
- BFS
- 싸피
- 모던 JavaScript 튜토리얼
- 2357
- 플로이드-워셜
- 정렬
- 수학
- DFS
- 애드 혹
- 맵
- JavaScript
- 그리디
- DP
- 이분 탐색
- 투 포인터
- boj
- 정수론
- 해시 테이블
- 에라토스테네스의 체
- 구현
- 브루트포스
- SSAFY
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 14712 - 넴모넴모 (Easy) (Python, JavaScript) 본문
아이디어
DFS로 넴모들을 격자판에 배치하고 2×2 사각형 칸에 모두 넴모가 배치된 경우는 더 탐색하지 않는다.
풀이 #1 (Python)
N이나 M이 1인 경우 2×2 사각형 칸이 존재할 수 없으므로 격자판에서 넴모를 배치하는 모든 경우의 수를 출력한다.
그렇지 않으면 넴모 배치를 위한 2차원 리스트 visited를 만드는데, 인덱스 에러 방지를 위해 행과 열 크기를 1씩 늘린다.
(1, 1)을 시작점으로 하여 방문 표시 후 함수 dfs를 호출하고, 시작점 방문 표시를 지우고 다시 함수 dfs를 호출한다.
함수 dfs에서는 현재 칸을 기준으로 현재 칸, 위쪽 칸, 왼쪽 칸, 좌상단 칸에 모두 넴모가 배치되면 백트래킹으로 종료한다.
격자판 한 행씩 왼쪽에서 오른쪽으로 넴모들을 배치해 나가고, 종료 없이 else문을 만나면 결과값 res를 1 증가시킨다.
# Python 3 기준 시간 초과, PyPy3 통과 코드
def dfs(i, j):
global res
if visited[i][j] and visited[i][j-1] and visited[i-1][j] and visited[i-1][j-1]:
return
if j < M:
visited[i][j+1] = 1
dfs(i, j+1)
visited[i][j+1] = 0
dfs(i, j+1)
elif i < N:
visited[i+1][1] = 1
dfs(i+1, 1)
visited[i+1][1] = 0
dfs(i+1, 1)
else:
res += 1
N, M = map(int, input().split())
if N == 1 or M == 1:
print(2**(N*M))
else:
res = 0
visited = [[0]*(M+1) for _ in range(N+1)]
visited[1][1] = 1
dfs(1, 1)
visited[1][1] = 0
dfs(1, 1)
print(res)
풀이 #2 (Python)
N과 M의 조합이 많지 않아 하드코딩으로 코드를 작성할 수도 있다.
N×M 격자판의 배치 가짓수는 M×N 격자판의 배치 가짓수와 같으므로 N이 M보다 작거나 같은 경우의 가짓수만 저장한다.
res = dict({(2, 2): 15, (2, 3): 57, (2, 4): 216, (2, 5): 819,
(2, 6): 3105, (2, 7): 11772, (2, 8): 44631, (2, 9): 169209,
(2, 10): 641520, (2, 11): 2432187, (2, 12): 9221121,
(3, 3): 417, (3, 4): 3032, (3, 5): 22077, (3, 6): 160697,
(3, 7): 1169792, (3, 8): 8515337, (4, 4): 42176, (4, 5): 587920,
(4, 6): 8191392, (5, 5): 15701273})
N, M = map(int, input().split())
if N == 1 or M == 1:
print(2**(N*M))
else:
if N > M:
N, M = M, N
print(res.get((N, M)))
풀이 #3 (JavaScript)
풀이 #1과 같은 방식으로 동작하며, 결과값을 저장하는 변수 res를 else문 내에 정의하면 에러가 발생한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function dfs(i, j) {
if (visited[i][j] && visited[i][j-1] && visited[i-1][j] && visited[i-1][j-1]) return;
if (j < M) {
visited[i][j+1] = 1;
dfs(i, j+1);
visited[i][j+1] = 0;
dfs(i, j+1);
}
else if (i < N) {
visited[i+1][1] = 1;
dfs(i+1, 1);
visited[i+1][1] = 0;
dfs(i+1, 1);
}
else res += 1;
}
const [N, M] = input[0].split(' ').map(Number);
let res = 0;
if (N == 1 || M == 1) console.log(2**(N*M));
else {
visited = Array.from(Array(N+1), () => Array(M+1).fill(0));
visited[1][1] = 1;
dfs(1, 1);
visited[1][1] = 0;
dfs(1, 1);
console.log(res);
}
'알고리즘' 카테고리의 다른 글
[BOJ] 3980 - 선발 명단 (Python, JavaScript) (0) | 2023.02.09 |
---|---|
[BOJ] 1509 - 팰린드롬 분할 (Python) (0) | 2023.02.09 |
[BOJ] 2631 - 줄세우기 (Python) (0) | 2023.02.08 |
[BOJ] 15658 - 연산자 끼워넣기 (2) (Python, JavaScript) (0) | 2023.02.07 |
[BOJ] 2011 - 암호코드 (Python) (0) | 2023.02.07 |
Comments