y-log

문제보러가기

🕵️‍♀️ 문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

💡 입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

📌 출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

🙋‍♀️ 풀어보자~

A가 B를 신뢰하는 형식이므로 입력을 x, y로 받고 arr[y].append(x)로 해주자.

bfs를 돌릴 때 arr[y]에 연결된 애들이 vistited 된적이 있는지 확인해보고 없으면 방문을 찍고 덱에 첨가해주는 형식으로 작성

from collections import deque

n, m = map(int, input().split())

arr = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    arr[y].append(x)

def bfs(v):
    q = deque([v])
    visited = [False] * (n + 1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in arr[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count

result = []
max_value = -1

for i in range(1, n+1):
    c = bfs(i)
    if c > max_value:
        result=[i]
        max_value=c
    elif c == max_value:
        result.append(i)
        max_value=c

for e in result:
    print(e, end=" ")

시간 초과 머선일이구,,,

문제보러가기

🕵️‍♀️ 문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

💡 입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

📌 출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

🙋‍♀️ 풀어보자~

우선 배추밭을 0으로 다 채워넣어야 한다.

그리고 그와 같은 크기로 false 인지 true인지를 담아줄 배열을 만든다. ( 왼쪽 상단이 (0, 0)이 되게 )

array=[[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

그리고 k번씩 돌면서 x, y 에 해당하는 값을 받아준다.

for _ in range(k):
    y, x = map(int,input().split())
    array[x][y] = 1

가로로 m까지 세로로 n까지 for문을 돌면서 array와 visited를 통해 배추는 심어져있지만 방문하지 않은 곳을 찾아 방문해주는 dfs나 bfs를 실행시키면된다.

for i in range(n):
    for j in range(m):
        if array[i][j] and not visited[i][j]:
            dfs(i,j) 나 bfs(i,j)

1. DFS로 풀 경우

재귀 용법을 사용할 것이다. 

파이썬의 재귀 깊이 제한은 1000으로 매우 얕기 때문에, 이 문제를 그냥 푼다면 런타임 에러가 난다.

파이썬으로 재귀를 사용해 풀어야하는 문제라면 setrecursionlimit를 쓰는 것은 선택이 아닌 필수다.

• 상하좌우로 움직일 수 있는 방향을 정해주고 이를 for문으로 돌린다.
• 각 위치의 값이 0보다 크고 최대 길이보다 작은지 1차적으로 확인을 해주고, 이에 해당되지 않는다면 continue를 사용해 다음 위치로 넘겨주게 for문으로 던진다.
• 맞다면 이젠 확인을 해준다. 이곳에 배추가 있고 방문한 적 이 없는가?

# 테스트 케이스 개수를 입력받는다.
# 만약 재귀를 사용해서 풀어야하는 문제라면 setrecursionlimit을 쓰는 것은 선택이 아닌 필수다.
# 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕다.
# 따라서 재귀로 문제를 풀경우 이제한에 걸려 에러메세지를 볼수 없다.
# 런타임 에러가 난다.
import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    visited[x][y] = True
    directions = [ (-1, 0), (1, 0), (0, -1), (0, 1)]
    # 상하 좌우로 움직일 수 있는 방향을 지정해주고 여기서 for문을 돌린다.
    for dx, dy in directions:
        nx, ny = dx + x, dy+y
        if nx < 0 or nx >=n or ny<0 or ny>=m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx,ny)

for _ in range(int(input())):
    m, n, k = map(int,input().split())
    array=[[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    for _ in range(k):
        y, x = map(int,input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i,j)
                result += 1
    print(result)

2. BFS로 풀어보면,,,

BFS는 덱..deque 

dfs와 마찬가지로 움직일 수 있는 상하좌우의 위치를 담아 for문을 돌려줄 것이다. 

from collections import deque

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if array[nx][ny] and not visited[nx][ny]:
                q.append((nx,ny))
                visited[nx][ny]=True


for _ in range(int(input())):
    m, n, k = map(int,input().split())
    array=[[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    for _ in range(k):
        y, x = map(int,input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                bfs(i,j)
                result += 1
    print(result)

문제보러가기

🕵️‍♀️ 문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

💡 입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

📌 출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

🙋‍♀️ 풀어보자~

com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)

for i in range(int(input())):
  x, y = map(int, input().split())
  adj[x].append(y)
  adj[y].append(x)

def dfs(v):
  visited[v] = True
  for e in adj[v]:
    if not visited[e]:
      dfs(e)
  
dfs(1)

for i in range(len(visited)):
  if visited[i] == True:
    cnt += 1
    
print(cnt-1)

2. BFS로 풀어보면,,,

from collections import deque

com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)

for i in range(int(input())):
  x, y = map(int, input().split())
  adj[x].append(y)
  adj[y].append(x)

def bfs(v):
  q = deque([v])
  visited[v] = True
  while q:
    v = q.popleft()
    for e in adj[v]:
      if not visited[e]:
        q.append(e)
        visited[e]= True

  
bfs(1)

for i in range(len(visited)):
  if visited[i] == True:
    cnt += 1

print(cnt-1)

문제보러가기

🕵️‍♀️ 문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

🙋‍♀️ 풀어보자~

DFS와 BFS로 풀 수 있는 문제다.

두 가지 방법을 모두 해보자!

1. DFS로 풀어보면,,,

• 방문을 했는지 확인을 도와줄 visited 배열을 사용한다.

def dfs(n, computers, com, visited):
  # dfs 돌기 위한 컴퓨터는 우선 방문했다고 찍는다.
  visited[com] = True
  
  # 컴퓨터들 개수만큼 for문 돌려서 com과 연결되어있고 방문한적 없는 것을 찾는다.
  # 찾으면 얘도 dfs돌린다.
  for connect in range(n):
    if connect != com and computers[com][connect] == 1:
      if visited[connect] == False:
        dfs(n, computers, connect, visited)


def solution(n, computers):
  answer = 0
  # 방문한 기록을 남기는 visited
  # 방문한 적이 없으면 False다.
  visited = [False] * n
  
  # 컴퓨터 한대씩 돌려보며 방문한 적 없는 컴퓨터를 찾아
  # dfs해주고, 한번 끝나면 answer에 1을 더해준다.
  for com in range(n):
    if visited[com] == False:
      dfs(n, computers, com, visited)
      answer += 1
      
  return answer;

2. BFS로 풀어보면,,,

dfs와 달리 deque 덱을 import 해줘야 한다.

from collections import deque

def bfs(n, computers, com, visited):
  # 덱에 현재 com 번호를 넣어준다.
  q = deque([com])
  
  # 방문했다고 표시해
  visited[com] = True
  
  # q를 돌리면서 popleft 해주고... 들려줘야하는 애면 append해준다
  while q:
    com = q.popleft()
    for connect in range(n):
      if connect!=com and computers[com][connect]==1 and not visited[connect]:
        q.append(connect)
        visited[connect] = True

def solution(n, computers):
  answer = 0
  visited = [False] * n
  for com in range(n):
    if visited[com] == False:
      bfs(n, computers, com, visited)
      answer += 1

  return answer;

문제보러가기

🕵️‍♀️ 문제

🙋‍♀️ 풀어보자~

1. 다리 위에 있는 트럭들의 리스트를 따로 만들자.

trucks_on_bridge -> 여기서 len는 bridge_length로 준다. 그 길이만큼만 트럭수가 들어갈 수 있기 때문

2. 이제 다리에 올라갈 수 있는 차 대수만큼 while문을 빌리면서 진행한다.

다리에 올라와 있는 트럭이 있으면 맨 앞에 있는 트럭을 빼주고

현재 다리에 있는 트럭들의 합과 새로 투입되기를 기다리는 truck_weights[0]을 합했을 때 견딜 수 있는지 체크한다.

된다면 다리에 올려주고 대기 목록에서 빼준다.

안된다면 그냥 0을 넣어서 올리지 못했음을 명시한다.

def solution(bridge_length, weight, truck_weights):
    answer = 0
    trucks_on_bridge = [0] * bridge_length
    while len(trucks_on_bridge):
        answer += 1
        trucks_on_bridge.pop(0)
        if truck_weights:
            if sum(trucks_on_bridge) + truck_weights[0] <= weight:
                trucks_on_bridge.append(truck_weights.pop(0))
            else:
                trucks_on_bridge.append(0)
    return answer

<참고할만한 답안>

import collections

DUMMY_TRUCK = 0


class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count


def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()

BOJ 14719

🕵️‍♀️ 문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

💡 입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

📌 출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

🙋‍♀️ 풀어보자~

빗물이 고이기 위해서는 기둥이 필요하다. 

이 기둥이 어떻게 생기는지 생각해보자.

위 사진과 같이 max인 4를 기준으로 좌우의 가장 큰 값인 3과 2의 값이 중요함을 알 수 있다.

왼쪽은 3을 기준으로 빗물이 받아지고 오른쪽은 2를 기준으로 빗물이 받아지기 때문~

더 자세하게 보자면..

각 자리를 i로 보고 0부터 7까지 번호를 매겼을 때 2번째 블럭을 보자.

i=2번째 블럭은 2개로 이 블럭을 기준으로 빗물 기둥이 되어줄 좌우의 max 숫자를 살펴보면 3과 4임을 알 수 있다.

여기서 max중 작은 수가 기준이 되기 때문에 3이라는 숫자를 이용해주게 된다.

정리하자면~

• 양쪽에 더 높은 블럭이 존재하면 빗물이 고임
• 반복문을 돌면서 현재의 블럭 기준 left_max와 right_max를 구하고 이 두 값중 작은 수를 구함
  • 구해진 수 - 현재 블럭의 수 가 빗물이 담길 칸수다.
  • 첫 블럭과 마지막 블럭은 볼필요 없다. (그림과 같은 예시를 이용하자면, i=0일 때와 i=7일 때)

# 빗물

# 입력을 받아 준다.
H, W = map(int, input().split())
block = list(map(int, input().split()))
answer = 0

# 맨 앞뒤를 제외한 for문을 돌면서 왼쪽과 오른쪽에서 최댓값을 찾는다.
for i in range(1, W-1):
    left_max = max(block[:i]) # 현재 블럭을 기준으로 왼쪽에서 max 값 찾기
    right_max = max(block[i+1:]) # 현재 블럭을 기준으로 오른쪽에서 max 값 찾기
    m = min(left_max, right_max) #left_max와 right_max 중 작은 값을 변수에 담자.
    
    # 현재 블럭이 지정한 기준값보다 작으면 빗물이 고인다.
    if block[i] < m:
        answer += m - block[i]

print(answer)

BOJ 1149

🕵️‍♀️ 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

💡 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

📌 출력

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
  
  

🙋‍♀️ 풀어보자~

다이나믹 프로그래밍으로 접근해서 Memoization을 사용하자.

2차원 배열을 이용해서 각 자리마다 RGB의 비용을 담을 수 있게 하자.

just like... -> [ [ 1번 집의 R비용, 1번 집의 G비용, 1번 집의 B비용 ] , [ 2번 집의 R비용, ....

점화식을 떠올리기 위해서 i번째의 집과 그 앞뒤의 i-1번째 집과 i+1번째 집을 생각해보자.

i+1번째 집은 i번째 집의 색에 영향을 받지만 i-1번째 집의 색에는 영향을 받지 않는다.

이 같은 상황을 점화식으로 생각해보자. i와 i+1만 생각해주면된다~

1. i+1번째 집이 R일 때, i-1은은 G나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
2. i+1번째 집이 G일 때, i-1은은 R나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
3. i+1번째 집이 B일 때, i-1은은 R나 G 중 더 적은 비용을 갖는 것을 선택하면 된다.

# RGB

# n : 집의 수
n = int(input())

# 초기세팅 0으로 다 깔아놓거라
dp = [[0, 0, 0] for _ in range(n)]

for i in range(n):
    # 우선 먼저 입력받음
    cost = list(map(int, input().split()))

    # 첫 입력인 경우, 그냥 cost를 담아주세요.
    if i == 0:
        dp[0] = cost
    else:
        # 점화식 넣어주세효
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[0] # i번째집이 R일경우
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[1] # i번째집이 G일경우
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[2] # i번째집이 B일경우

# dp 리스트의 n-1번째에 있는 누적된 RGB 비용 중 가장 최소 값을 출력한다.
print(min(dp[n-1]))

46. Permutations

🕵️‍♀️ Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

💡 Example

1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2:

Input: nums = [0,1]

Output: [[0,1],[1,0]]

3:

Input: nums = [1]

Output: [[1]]

📌 Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

🙋‍♀️ 풀어보자~

서로 다른 정수를 입력받아 가능한 모든 수열을 리턴하는 간단한 순열 문제다.

두가지의 풀이가 존재한다.

version1 : DFS를 활용한 순열 생성

백트래킹(backtracking)이란? :

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.

최적화 문제와 결정 문제를 푸는 방법이 됩니다.

순열이란 모든 가능한 경우를 그래프 형태로 나열한 결과이다. -> 그래프로 표현 가능하다.

# Runtime: 69 ms
# Memory Usage: 14.4 MB

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []
        
        def dfs(elements) :
            #리프노드일때
            if len(elements) == 0 :
                results.append(prev_elements[:])
                
            #순열 생성 재귀 호출
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
               
                prev_elements.append(e)
                # print("perv",prev_elements)
                # print("next재귀돌러가즈아",next_elements)
                dfs(next_elements)
                prev_elements.pop()
                # print("**백트래킹",prev_elements)
    
        dfs(nums) 
        return results

# input이 [1,2,3] 면 나오는 출력,,,
perv [1]
next재귀돌러가즈아 [2, 3]
perv [1, 2]
next재귀돌러가즈아 [3]
perv [1, 2, 3]
next재귀돌러가즈아 []
**백트래킹 [1, 2]
**백트래킹 [1]
perv [1, 3]
next재귀돌러가즈아 [2]
perv [1, 3, 2]
next재귀돌러가즈아 []
**백트래킹 [1, 3]
**백트래킹 [1]
**백트래킹 []
perv [2]
next재귀돌러가즈아 [1, 3]
perv [2, 1]
next재귀돌러가즈아 [3]
perv [2, 1, 3]
next재귀돌러가즈아 []
**백트래킹 [2, 1]
**백트래킹 [2]
perv [2, 3]
next재귀돌러가즈아 [1]
perv [2, 3, 1]
next재귀돌러가즈아 []
**백트래킹 [2, 3]
**백트래킹 [2]
**백트래킹 []
perv [3]
next재귀돌러가즈아 [1, 2]
perv [3, 1]
next재귀돌러가즈아 [2]
perv [3, 1, 2]
next재귀돌러가즈아 []
**백트래킹 [3, 1]
**백트래킹 [3]
perv [3, 2]
next재귀돌러가즈아 [1]
perv [3, 2, 1]
next재귀돌러가즈아 []
**백트래킹 [3, 2]
**백트래킹 [3]
**백트래킹 []
=========
perv [0]
next재귀돌러가즈아 [1]
perv [0, 1]
next재귀돌러가즈아 []
**백트래킹 [0]
**백트래킹 []
perv [1]
next재귀돌러가즈아 [0]
perv [1, 0]
next재귀돌러가즈아 []
**백트래킹 [1]
**백트래킹 []

version2. 파이썬의 itertools 모듈을 사용한다.

itertools 
반복자 생성에 최적화된 효율적인 기능들을 제공.
이미 잘 구현된 라이브러리라 버그 발생 가능성이 낮고 효율적으로 설계된 C 라이브러리라 속도도 빠름
📍 사용할 때 주석으로 "# 구현의 효율성, 성능을 위해 사용했다" 라고 달아주면 쵝오~

permutation( ) 함수가 튜플 모음을 반환하기 때문에 리트코드 문제에서는 리스트를 반환하도록 요구하기 때문에 변환처리를 해줘야한다.

# Runtime: 28 ms
# Memory Usage: 14.3 MB

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import itertools
        return list(map(list, itertools.permutations(nums)))