15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

<내 코드>

 

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []

def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            arr.pop()  # 탐사한 내용 제거

            # 순열 부분과의 차이점
            for j in range(i+1, N):
                visited[j] = 0

dfs(0)

 

처음 i의 DFS 탐색에 사용 된 i값을 제외시키는 것이 순열과 다른 조합의 차이다.

 

 

파이썬 itertools 모듈의 combinations를 사용한 방법

 

from itertools import combinations

N, M = map(int, input().split())

p = combinations(range(1, N+1), M)
for i in p:
    print(*i)
반응형

 

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

<내 코드>

 

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색

            visited[i] = 0  # 탐사 완료 후 다시 초기화
            arr.pop()  # 탐사한 내용 제거


dfs(0)

 

DFS와 백트래킹을 이용해 푸는 문제다. 재귀가 사용되다 보니 이해를 하는데 꽤 힘들었다.. 

 

 

파이썬 itertools 모듈을 사용한 방법

 

from itertools import permutations

N, M = map(int, input().split())

p = permutations(range(1, N+1), M)
for i in p:
    print(*i)

 

반응형

 

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

 

 

<내 코드>

 

from collections import deque


def bfs():

    while q:
        s, c = q.popleft()
        # 복사, 붙여넣기, 삭제 후 1초씩 증가 && 다녀간 곳 q에 추가
        # 복사
        if check[s][s] == -1:
            check[s][s] = check[s][c] + 1
            q.append((s, s))
        # 붙여넣기
        if s+c <= S and check[s+c][c] == -1:
            check[s+c][c] = check[s][c] + 1
            q.append((s+c, c))
        # 삭제
        if s-1 >= 0 and check[s-1][c] == -1:
            check[s-1][c] = check[s][c] + 1
            q.append((s-1, c))


S = int(input())
q = deque()
MAX = 1001
check = [[-1]*MAX for _ in range(MAX)]

check[1][0] = 0
q.append((1, 0))

bfs()

ans = -1
for i in range(S):
    if check[S][i] != -1:
        if ans == -1 or ans > check[S][i]:
            ans = check[S][i]
print(ans)

 

처음에 문제를 복사 - 붙여 넣기 - 복사- 붙여 넣기... 하는 것으로 잘못 이해했었다. 실제로는 클립보드에 들어있는 이모티콘은 여러 번 화면에 붙여 넣기가 가능한 것이다.

이 문제는 기존의 BFS 문제랑 조금 차이가 있다. 기존에는 입력을 그래프 형태로 주어졌는데, 이 문제는 본인이 새로 그래프를 만들어야 했다. 복사, 붙여넣기, 삭제 부분을 작성하고 현재 s,c에 대한  시간 check [s][c] 값에 +1초씩 해준다.  그리고 찾고자 하는 입력 값 check [s] 중 최솟값을 찾아 출력하면 된다.

반응형

 

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

 

 

<내 코드>

 

import heapq
import sys


def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while(q):

        cnt, x, y = heapq.heappop(q)  # (0,0,0)형식
        done[x][y] = 1

        if x == N-1 and y == M-1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < N) and (0 <= ny < M) and done[nx][ny] == 0:
                done[nx][ny] = 1

                # 길이 있는 경우 우선순위(최소힙)가 가도록 한다.
                if maps[nx][ny] == '0':
                    heapq.heappush(q, (cnt, nx, ny))
                elif maps[nx][ny] == '1':
                    heapq.heappush(q, (cnt+1, nx, ny))
                


M, N = map(int, sys.stdin.readline().split())
maps = [list(str(sys.stdin.readline())) for _ in range(N)]
q = []
done = [[0]*M for _ in range(N)]

heapq.heappush(q, (0, 0, 0))

print(bfs())

BFS와 우선수위 큐를 이용하는 독특한 문제이다. 처음에는 BFS로만 문제를 풀려고 했지만 어려웠다.

heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 있는 채로 BFS를 해야하기 때문이다.

여기서 길(0)이 있다면 우선순위를 줘서 그 길부터 가도록 한다. 만약 길이 없고 벽(1)만 있다면 cnt+1을 해줘 벽을 부순다. 우선순위가 낮은 값부터 탐색하게 되서 원하는 동작이 구현된다.

 

반응형

+ Recent posts