백트래킹 (N과 M)
백트래킹?
해를 찾는 도중 아니라면, 되돌아가서 다시 해를 찾아가는 기법
N과 M
대표적 백트래킹 문제들이다. 조금 더 간결한 코드를 작성할 수 있지만, 좀 더 복잡한 문제에서도 풀기 위해 visit 리스트를 추가해 풀었다.
N과 M (1)
https://www.acmicpc.net/problem/15649
- 조건 : 중복되면 안된다.
n, m = map(int, input().split())
visit = [False for _ in range(n+1)]
def sol(level, ansList):
if level > m:
print(' '.join(map(str, ansList)))
return
for i in range(1, n+1):
if not visit[i]:
visit[i] = True
ansList.append(i)
sol(level+1, ansList)
ansList.pop()
visit[i] = False
sol(1, [])
# 4 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
N과 M (2)
https://www.acmicpc.net/problem/15650
- 조건 : 중복되면 안되며, 오름차순이어야함.
n, m = map(int, input().split())
visit = [False for _ in range(n+1)]
def sol(level, ansList):
if level > m:
print(' '.join(map(str, ansList)))
return
for i in range(1, n+1):
if not visit[i]:
if ansList:
if ansList[-1] >= i:
continue
visit[i] = True
ansList.append(i)
sol(level+1, ansList)
ansList.pop()
visit[i] = False
sol(1, [])
# 4 2
1 2
1 3
1 4
2 3
2 4
3 4
N과 M (3)
https://www.acmicpc.net/problem/15651
- 조건 : 중복 가능
n, m = map(int, input().split())
visit = [False for _ in range(n+1)]
def sol(level, ansList):
if level > m:
print(' '.join(map(str, ansList)))
return
for i in range(1, n+1):
ansList.append(i)
sol(level+1, ansList)
ansList.pop()
sol(1, [])
# 4 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
N과 M (4)
https://www.acmicpc.net/problem/15652
- 조건 : 중복 가능하며, 같거나 오름차순
n, m = map(int, input().split())
visit = [False for _ in range(n+1)]
def sol(level, ansList):
if level > m:
print(' '.join(map(str, ansList)))
return
for i in range(1, n+1):
if ansList:
if ansList[-1] > i:
continue
ansList.append(i)
sol(level+1, ansList)
ansList.pop()
sol(1, [])
# 3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3
Author And Source
이 문제에 관하여(백트래킹 (N과 M)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jun-k0/백트래킹-N과-M저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)