백준 2210 숫자판 점프 Python3

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2210_dfs.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def dfs(cnt, x, y, num):
    global nums
    if cnt == 6:
        nums.add(num)
        return

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            dfs(cnt+1, nx, ny, num+board[ny][nx])
    
global nums
board = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
nums = set()
for _ in range(5):
    board.append(list(sys.stdin.readline().split()))
for i in range(5):
    for j in range(5):
        dfs(1, j, i, board[i][j])
print(len(nums))

 

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2210_bfs.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
def bfs(sx, sy):
    global nums
    q = deque()
    q.append([sx, sy, board[sy][sx]])
    while q:
        x, y, num = q.popleft()
        if len(num) == 6:
            nums.add(num)
            continue
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<5 and 0<=ny<5:
                q.append([nx, ny, num+board[ny][nx]])

global nums
board = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
nums = set()

for _ in range(5):
    board.append(sys.stdin.readline().split())

for i in range(5):
    for j in range(5):
        bfs(i, j)

print(len(nums))

---

풀이 과정

풀이 시간 14분

1. DFS

import sys
def dfs(cnt, x, y, num):
    global nums
    #6자리가 만들어진 경우, 집합 nums에 num을 추가
    if cnt == 6:
        nums.add(num)
        return
	#인접한 네 방향 탐색
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            dfs(cnt+1, nx, ny, num+board[ny][nx])
    
global nums
board = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
nums = set()
for _ in range(5):
    board.append(list(sys.stdin.readline().split()))
for i in range(5):
    for j in range(5):
        dfs(1, j, i, board[i][j])
print(len(nums))
#시간복잡도 = O(V(V+E)) = O(V^2), 공간복잡도 = O(V^2)
#V = 25, E = 4V = 100 -> 총 25(25+100) = 3125번의 연산 필요
#6자리를 만드는 경우의 수만큼 집합 자료구조 공간 할당 필요 -> DFS 호출 횟수 만큼

 

2. BFS

import sys
from collections import deque
def bfs(sx, sy):
    global nums
    q = deque()
    q.append([sx, sy, board[sy][sx]])
    while q:
        x, y, num = q.popleft()
        #6자리가 만들어진 경우, 집합 nums에 추가
        if len(num) == 6:
            nums.add(num)
            continue
        #인접한 네 방향 탐색
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<5 and 0<=ny<5:
                q.append([nx, ny, num+board[ny][nx]])

global nums
board = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
nums = set()

for _ in range(5):
    board.append(sys.stdin.readline().split())

for i in range(5):
    for j in range(5):
        bfs(i, j)

print(len(nums))
#시간복잡도 = O(V(V+E)) = O(V^2), 공간복잡도 = O(V^2)
#V = 25, E = 4V = 100 -> 총 25(25+100) = 3125번의 연산 필요
#6자리를 만드는 경우의 수만큼 집합 자료구조 공간 할당 필요 -> DFS 호출 횟수 만큼 공간 할당