[문제]https://www.acmicpc.net/problem/32620그래프를 탐색하는 데 있어서, 이웃 노드를 하나 이상 점령한다는 점에서 BFS 탐색을 떠올렸습니다. 또한 i번 노드로 이동하는 데 있어, 현재 기력이 요구하는 기력 이상이라면 이동할 수 있다는 점에서 그리디 접근 법을 떠올렸습니다. 즉 이동하고자 하는 노드와 인접한 노드를 방문한 상태이고, 요구하는 기력이 현재 기력 이하라면 모든 노드를 탐색할 수 있다는 점에서 최대한 많은 노드를 탐색해야 얻을 수 있는 기력을 최대로 만들 수 있습니다. 그렇기 때문에 BFS 탐색에 사용하는 자료구조로 일반적인 큐를 사용하지 않고 우선순위 큐를 사용해, 인접하면서 요구하는 기력이 작은 순으로 탐색하는 것입니다. 요약하자면다음 노드를 방문하기 위해서는..
백준
[문제]https://www.acmicpc.net/problem/21608기본적인 구현문제로, 주어진 조건대로 착실하게 수행하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.student_info = [tuple(map(int, input().split())) for _ in range(self.n**2)] self.score = {0: 0, 1: 1, 2: 10, 3: 100, 4: 1000} self.grid = [[0] * self.n for _ in range(self.n)] self.friends_list = defaultdict(set) self.a..
[문제]https://www.acmicpc.net/problem/1937 전체적인 탐색을 진행하는 문제로, 이동에 제약이 걸려있는 것이 특징입니다. 시작점이 정해져 있다면, 주어진 대로 탐색을 진행하면 되지만 이동하는 칸을 최대로 만들어야 하기 때문에 시작점을 특정할 수 없습니다. 러프하게 생각하면 주어진 격자를 전부 탐색하면서 DFS를 수행하면 되겠지만, 시간 초과가 발생하므로 이동한 내역을 따로 기록해서 불필요한 이동을 막아줘야 합니다. 이때 사용되는 개념이 DP로, 해당 문제는 DFS + DP가 혼합된 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.graph = [list(map(int, input().spl..
[문제]https://www.acmicpc.net/problem/1599요즘 코테를 보면 문자열 문제가 많이 출제되고 있는 거 같습니다. 특정 유형이 정해진 문제가 아니라면 아이디어로 구현하는 느낌이라 개인적으로 어렵게 다가오는 유형 중 하나입니다. 문제의 요지는 새로운 문자 체계를 기준에 맞게 정렬하는 문제입니다. 문자 정렬은 문자 하나하나의 아스키 값을 바탕으로 정렬하기 때문에, 새로운 문자 체계에 맞는 키 값을 매핑하는 방식으로 문제를 해결했습니다.[초기화] def __init__(self): self.n = int(input()) self.words = [input() for _ in range(self.n)] self.answer = [](키, 값) 형..
[문제]https://www.acmicpc.net/problem/14499주사위를 굴릴 때마다 주사위가 어떻게 변화하는지 시뮬레이션하는 문제입니다. 주사위를 "굴린다." 라는 표현에서 값들이 회전한다는 느낌을 받았고, 자연스럽게 Deque 자료구조를 떠올릴 수 있었습니다.[초기화] def __init__(self): self.n, self.m, self.y, self.x, self.k = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.commands = list(map(lambda x: int(x) - 1, input().split..
[문제]https://www.acmicpc.net/problem/2458처음에는 어떻게 풀어야 할지 고민했습니다. 그런데 그래프 이미지 하단에 설명을 보고 연결된 그리고 연결한 노드의 수가 n - 1일 때 등수를 알 수 있다는 것을 알게 됐고, 진입 노드의 수 + 진출 노드의 수를 계산하면 답을 구할 수 있겠다고 생각했습니다. 이를 위해 진입 그래프와 진출 그래프를 만들고 두 번의 DFS를 수행했습니다. 굉장히 부르트포스한 방법인데, Python 기준 3000ms대로 풀이가 통과됐고, 입력을 sys를 받았을 때 위와 같은 시간대로 통과됐습니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self...
[문제]https://www.acmicpc.net/problem/7490 단순한 백트래킹에 공백이라는 조건을 추가해서 약간의 생각을 하게 만드는 문제였습니다.[초기화] static ArrayList results; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for (int t = 0; t (); search("1", 1, 1, 1)..
[문제]https://www.acmicpc.net/problem/2109그리디하게 매 순간 가장 큰 강의료를 받을 수 있는지 확인하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.schedule = [list(map(int, input().split())) for _ in range(self.n)] self.visited = [False] * 10001 self.answer = 0강의는 특정 일자에 진행하는 것이 아닌, 제안받은 시점으로부터 d일 안에만 가서 강의를 진행하면 됩니다. visited는 이를 위해 어느 시점에 방문했는지 확인하기 위한 용도로 사용될 것입니다.[풀이] ..
[문제]https://www.acmicpc.net/problem/16954생각보다 손이 많이 갔던 문제입니다. 처음에 놓쳤던 부분은 벽이었습니다. 벽을 내릴 때, 순차적으로 내리지 않고 입력받은 순으로 처리하다 보니 잘못된 처리가 수행되었습니다. 다음으로 놓쳤던 부분은 이동한 벽과 캐릭터가 만났을 때 처리하는 것이었습니다, BFS를 사용하게 되면 하나의 방향이 아니라 이동 가능한 9개의 방향과 움직인 벽을 고려해야 하는데, 이를 어떻게 처리해야 할지 고민하는 데 많은 시간을 소요했습니다.[초기화] def __init__(self): self.grid = [list(input()) for _ in range(8)] self.walls = set((i, j) for i in r..
[문제]https://www.acmicpc.net/problem/18428백트래킹과 BFS가 조합된 문제입니다. 백트래킹을 통해 3개의 벽을 설치할 수 있는 경우의 수를 만들고, 모든 벽을 쌓았을 때 선생님이 학생들을 모두 찾아낼 수 있는지 확인하면 되겠습니다.[초기화] def __init__(self): self.n = int(input()) self.grid = [input().split() for _ in range(self.n)] self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] self.teacher_pos = [[i, j] for j in range(self.n) for i in range(se..
