[백준 2024/03/29] 15650번 N과 M (2)

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

15650번: N과 M (2)

 

1. 접근 방법

이번 문제는 DFS로 접근해야겠다는 냄새가 많이 나는 문제였다.

 

def DFS(rows, m):
    if len(rows) == m:
        print(' '.join(map(str, rows)))
        return
    for i in range(1, n + 1, 1):
        if len(rows) == 0 or rows[-1] < i:
            rows.append(i)
            DFS(rows, m)


n, m = map(int, input().split())
DFS([], m)

 

처음에는 위와 같이 코드를 작성했었다.

하지만, 

1

2

3 으로 출력되어야 할 것이

1만 출력되고 끝나버렸다.

 

이유가 뭘까 하고 debugging을 해보니, rows.append(i)를 하니, [1, 2] 로 값이 저장이 되어, DFS로 넘어가는 것을 확인하였다.

사실은 [2]만 전달되어야 함에도 불구하고

따라서 DFS(rows + [i], m) 으로 값을 전달해주니, 원래의 rows에 영향을 미치지 않고 값을 전달해 줄 수 있었다.

 

2. 코드

def DFS(rows, m):
    if len(rows) == m:
        print(' '.join(map(str, rows)))
        return
    for i in range(1, n + 1, 1):
        if len(rows) == 0 or rows[-1] < i:
            DFS(rows + [i], m)


n, m = map(int, input().split())
DFS([], m)