본문 바로가기

👨‍💻📱✍️🎢314

BOJ 10472 - 십자뒤집기 문제 백준 온라인 저지 - 10472번 풀이 과정 보드의 최종 상태가 주어질 때, 초기 상태에서 해당 목표 상태에 도달하기 위한 최소 조작 횟수를 구하는 문제입니다. 이를 위해서 BFS 를 이용해 보드의 모든 가능한 상태를 순회해줍니다. 다만 중복된 상태 순회를 피하기 위해서 보드가 검은색으로 칠해져 있을 경우 1 로, 그렇지 않을 경우 0 으로 변환하여 이진수를 생성한 다음, 중복된 상태를 검증합니다. 코드 import sys import copy from collections import deque dx = [0, 1, -1, 0, 0] dy = [0, 0, 0, 1, -1] def convert_board(board, x, y): ret = copy.deepcopy(board) for i in ra.. 2021. 4. 18.
BOJ 13908 - 비밀번호 문제 백준 온라인 저지 - 13908번 풀이 과정 비밀번호에 포함된 숫자들을 알고 있을 때 가능한 모든 경우의 수를 찾는 문제입니다. 백트래킹 을 이용해서 모든 경우의 수를 따져본 다음, 생성된 비밀번호가 조건에 부합하는지 판단하면 됩니다. 코드 import sys def is_valid(password): return all(map(lambda num: num in password, nums)) def dfs(password): if len(password) == n: return 1 if is_valid(password) else 0 ret = 0 for i in range(10): password.append(i) ret += dfs(password) password.pop() return ret .. 2021. 4. 13.
BOJ 14940 - 쉬운 최단거리 문제 백준 온라인 저지 - 14940번 풀이 과정 목표지점에 도달하기 위한 최단거리를 구하는 문제입니다. 2차원 배열의 각 칸을 정점이라고 생각할 경우 모든 인접한 정점까지의 거리 값은 같기 때문에 BFS 를 이용해서 목표지점까지의 최단 거리를 구할 수 있습니다. 코드 import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def find_start(): for x in range(N): for y in range(M): if board[x][y] == 2: return [x, y] def in_range(x, y): return 0 2021. 4. 13.
BOJ 16441 - 아기돼지와 늑대 문제 백준 온라인 저지 - 16441번 풀이 과정 BFS 를 이용해서 아기돼지가 안전하게 위치할 수 있는 장소들을 찾는 문제입니다. 모든 늑대들의 초기 위치를 찾은 다음, 큐에 넣고 초기화시킵니다. 이후 늑대들을 기준으로 BFS 를 수행하며 늑대들이 방문 가능한 위치를 표시합니다. 만약 늑대가 빙판을 만난다면 이동중인 방향을 기준으로 벽이나 잔디를 만날때까지 이동합니다. 코드 import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def preprocess(): wolves = [] for n in range(N): for m in range(M): if board[n][m] == 'W': wolves.a.. 2021. 4. 13.
BOJ 1922 - 네트워크 연결 문제 백준 온라인 저지 - 1922번 풀이 과정 모든 컴퓨터를 연결하는 네트워크를 구성하는 최소 비용을 구하는 문제입니다. 크루스칼 알고리즘 을 이용해서 MST 를 구현했으며 union 연산에서는 랭크 최적화와 경로 압축을 사용했습니다. 코드 import sys def union(v1, v2): r1, r2 = find(v1), find(v2) if r1 == r2: return if rank[r1] > rank[r2]: parent[r2] = r1 else: parent[r1] = r2 if rank[r1] == rank[r2]: rank[r2] += 1 def find(v): if parent[v] != v: parent[v] = find(parent[v]) return parent[v] def kr.. 2021. 4. 13.
BOJ 20006 - 랭킹전 대기열 문제 백준 온라인 저지 - 20006번 풀이 과정 랭킹 대기열 로직을 구현하는 문제입니다. 먼저 방의 정보를 관리하기 위해 해시 테이블 을 사용했습니다. 이때 해당 방에 방장의 식별자와 참여중인 다른 사람들을 배열 형태로 관리합니다. 여기서 assign_player 함수에서는 플레이어를 기존에 존재하는 방에 할당 가능한지 판단하고 만약 새로운 방이 필요할 경우 방장으로 할당한 뒤 새로운 방을 생성하도록 합니다. 코드 import sys def assign_player(player_id, player_level, rooms): for _, meta in rooms.items(): master_level = players[meta['master']] if master_level - 10 2021. 4. 13.

티스토리툴바