분류 전체보기

[백준] 9663. N-Queen

📌문제 https://www.acmicpc.net/problem/9663 🎖️난이도 ✔️풀이 # sol1) 재귀 # python3 오답 (시간 초과) & pypy3 정답 (30044ms) n = int(input()) queen = [0 for _ in range(n)] # 각 행마다의 퀸의 위치(열) cnt = 0 # 해당 행에 퀸을 놓을 수 있는 곳이 있는지(유망한지) 현재 queen 배열 상태 체크 def isPromising(row): # 체크하려는 행의 이전 행까지만 체크 for i in range(row): # 퀸을 놓을 수 없는 경우 2가지 (유망 x) # 1. 같은 열에 위치한 퀸이 있거나 or 2. 왼쪽 위 or 오른쪽 위 대각선에 퀸이 있거나 if queen[row] == queen[i..

[백준] 15651. N과 M (3)

📌문제 https://www.acmicpc.net/problem/15651 🎖️난이도 ✔️풀이 from itertools import product # 중복 순열 n, m = map(int, input().split()) for i in product(range(1, n+1), repeat = m): # product는 꼭 repeat!! print(' '.join(map(str, i)))

[백준] 15650. N과 M (2)

📌문제 https://www.acmicpc.net/problem/15650 🎖️난이도 ✔️풀이 n, m = map(int, input().split()) result = [] def dfs(k): if len(result) == m: print(' '.join(map(str, result))) for i in range(k, n+1): if i not in result: result.append(i) dfs(i+1) # 다음 값부터 dfs 돌도록 넣기! result.pop() dfs(1)

[백준] 15649. N과 M (1)

📌문제 https://www.acmicpc.net/problem/15649 🎖️난이도 ✔️풀이 # sol1) back tracking (recursion) N, M = map(int, input().split()) result = list() def func(): if len(result) == M: print(' '.join(map(str, result))) return for i in range(1, N+1): if i not in result: result.append(i) func() result.pop() func() # sol2) itertools - permutations (순열) from itertools import permutations n, m = map(int, input().spl..

[백준] 2178. 미로 탐색

📌문제 https://www.acmicpc.net/problem/2178 🎖️난이도 ✔️풀이 # 정답 - bfs (visited, queue) from collections import deque n, m = map(int, input().split()) miro = [list(map(int, list(input()))) for _ in range(n)] visited = [[0]*m for _ in range(n)] # ~까지의 이동 횟수(방문한 칸 수) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # bfs q = deque() q.append([0, 0]) # 시작 위치 visited[0][0] = 1 # 시작 위치까지의 방문 칸 수 1칸 # 큐가 빌 때까지 반복 while ..