문제 링크 문제 해결 별다른 조건이 없는 DFS, BFS 문제 입력으로 주어지는 정점은 key로 하고 각 간선들을 담는 리스트를 value로 하여 dictionary 자료형으로 구현하였다. 정석적인 방법으로 DFS는 초기 정점으로 시작하여 정점이 가지고있는 간선들을 순회하면서 재귀호출로 풀고, BFS는 간선들을 순회하면서 queue에 추가하는 방식으로 풀이하였다. 처음에 양방향의 조건을 못보고 단방향 그래프로 구현했다가 테케2번이 꼬여서 잠깐 헤맸다. 이전에 c++로 풀었던 풀이가 있어서 봤는데, 그래프를 key,value형태가 아닌 2차원 배열로 저장하여 풀었었다. 이 방법도 나중에 다시 파이썬 이중리스트로 구현해서 속도를 비교해봐야겠다....
문제 링크 문제 해결 초기 접근은 너비(width)를 기준으로 1부터 최대길이까지 각 width에 맞는 height를 전부 탐색 현재 조건에서 brown + yellow = 높이 * 너비를 만족하면 정답 리턴 이런식으로 구현하였다가, 일부 케이스에서 실패 및 시간초과가 나왔다. 직사각형을 만들기 위해 리스트를 append하는 부분에서 효율적이지 못한 코드였다. 문제의 조건을 다시 보고, 특정 w,h에서 yellow와 brown이 만족하는 조건에 초점을 맞춰서 다시 구현하였다. 기존 풀이방법의 width를 기준으로 height를 순회하는 방법을 사용하되, 조건을 각 w,h일때 입력으로 주어진 brown,yellow가 되는조건을 검사하여 해결하였다....
문제 링크 문제 해결 bfs를 이용하여 풀었다. 현재위치 (1,1)에서 맵을 탐색해 나가면서 벽이 있으면 카운팅, 없으면 계속해서 탐색한다. 단, 최소한의 갯수로 벽을 부숴 도착지로 이동해야 하므로 경로좌표를 queue에 삽입할 때, 빈 공간이 있으면 해당 좌표를 우선순위로 삽입하여 불 필요한 벽을 카운팅하는 일이 없도록 해야한다. 코드 from collections import deque # move helper mx = [0, 0, -1, 1] my = [1, -1, 0, 0] def check_range(x, y: int): return x < m and y < n and x >= 0 and y >= 0 def solve(): paths = deque() paths....
문제 링크 문제 해결 N번째 감소하는 수가 몇인지 출력하는 문제, N은 최대 100만까지 입력된다. 간단하게 0부터 987654321까지 감소하는 수인지 판별하는것은 시간초과가 나오므로, 감소하는 수의 특성을 이용하여 풀어야한다. 감소하는 수는 955같이 중복이 나오면 안되고 맨 앞자리의 수에 의해 나머지가 결정된다. 예를들어 특정 감소하는 수가 5로 시작된다면 나머지는 반드시 {1,2,3,4}의 조합으로 이루어져야 한다. 이런 성질을 이용해서 1부터 10까지 대표 앞자리를 설정한 후 각 앞자리마다 파생되는 나머지 숫자들을 조합하면 된다. 1 10 21 -> 210 -> 20 -> 20 32 -> 321 -> 3210 -> 320 31 -> 310 30 43 -> 432 -> 4321 -> 43210 -> 431 -> 430 ....
문제 링크 문제 해결 맵에 있는 탐색 가능한 모든 문서의 갯수를 찾는 문제로, BFS를 이용하여 풀었다. 특이한 점은 주어진 열쇠로 맵에 있는 문을 열어서 이동할 수 가 있다는것인데, 열쇠를 맵을 탐색하면서 추가적으로 획득할 수 있기 때문에 이 부분을 유의하여 풀어야 한다. 입력 for _ in range(int(input())): height, width = map(int, input().split()) floor = [list(input()) for _ in range(height)] keys = set(input()) visited = [[0 for _ in row] for row in floor] documents = 0 doors = {} # 열리지 않은 문 리스트 for door in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": doors....