Algorithm-암호 만들기

in Algorithm, Back Tracking

백준 1759 : 문제링크

  • 문제유형 :

    • 백 트레킹

  • 설명

    • C개의 문자들중에서 L개를 선택하는 모든 조합을 고려한다
    • 모음의 개수와 자음의 개수 조건을 확인한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    import copy

    result = []
    string = []

    def combination(array, length, index):
        if len(string) == length:
            result.append(copy.deepcopy(string))
            return
        for i in range(index, len(array)):
            string.append(array[i])
            combination(array, length, index + 1)
            string.pop()

    vowels = ('a', 'e', 'i', 'o', 'u')
    l, c = map(int, input().split(' '))

    array = input().split(' ')
    array.sort()

    combination(array, l, 0)

    for password in result:
        count = 0:
        for i in password:
            if i in vowels:
                count += 1
        
        if count >= 1 and count <= l - 2:
            print(''.join(password))

Comment and share

Algorithm-알파벳

in Algorithm, Back Tracking

백준 1987 : 문제링크

  • 문제유형 :

    • 백 트레킹

  • 설명

    • 말을 상하좌우 네 가지 방향으로 이동시킨다
    • 지금까지 지나온 모든 칸에 적힌 알파벳과 다른 알파벳이 적인 칸으로 이동
    • 백 트레킹을 이용하여 다른 알파벳이 적힌 칸으로 이동하도록 한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    def bfs(x, y):
        global result
        q = set()
        q.add((x, y, array[x][y]))

        while q:
            x, y, step = q.pop()
            result = max(result, len(step))

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
            
                if (0 <= nx and nx < r and 0 <= ny and ny < c 
                    and array[nx][ny] not in step)
                    q.add(nx, ny, step + array[nx][ny])
        
    r, c = map(int, input().split())
    array = []
    for _ in range(r):
        array.append(input())

    result = 0
    bfs(0, 0)
    print(result)

Comment and share

Algorithm-N Queen

in Algorithm, Back Tracking

백준 9663 : 문제링크

  • 문제유형 :

    • 백 트레킹

  • 설명

    • DFS를 이용하여 백트래킹 알고리즘을 구현한다
    • 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려한다
    • 이 때 위쪽 행을 모두 확인하며, 현재 위치에 놓을 수 있는지 확인한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def check(x):
        for i in  range(x):
            if row[x] == row[i]:
                return False
            if abs(row[x] - row[i]) == x - i:
                return False
        return True

    def dfs(x):
        global result
        if x == n:
            result += 1
        else:
            for i in range(n):
                row[x] = i
                if check(x):   
                    dfs(x+1)
        
    n = int(input())
    row = [0] * n
    result = 0
    dfs(0)
    print(result)

Comment and share

  • page 1 of 1

Yechan Kim

author.bio


author.job