본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 16174번 python 풀이 - dfs https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제의 핵심을 파악하는 것이 중요하다. 출발점은 정사각형의 가장 왼쪽, 가장 위의 칸이라는 점 이동 가능한 방향은 오른쪽과 아래 뿐이라는 점 가장 오른쪽 아래에 도착하면 승리한다는 점 이동할 수 있는 칸은 배열에 적혀있는 칸의 크기라는 점 dfs 함수 재귀적 호출을 하며 도착지에 도착했을 경우 "HaruHaru" 출력 실패했을 경우 "Hing" 출력 import sys sys.setrecursionl.. 2023. 4. 3.
[백준/BOJ] - 15900번 python 풀이 - dfs 성원이와 형석이가 번갈아가며 리프 노드에 있는 말을 옮기는 동작을 수행한다. 승리 조건은 자기 손으로 직접 현존하는 말을 모두 없애버리는 것이다. 성원이가 먼저 시작한다고 하였기에 리프노드의 depth의 합이 홀수라면 성원이가 이기게 될 것이다. ex) 리프노드의 depth의 합이 1이라고 가정하면 성원이가 말을 한번 옮기는 순간 현존하는 말이 모두 없어진다. 결국, 노드 마다 depth의 값을 저장하고 그 중 리프노드를 걸러내어 그 depth의 합이 짝수인지 홀수인지 여부를 따지면 된다. 시간초과가 나서 pypy3로 해결. 정확히 무슨 이유인지는 모르겠지만 재귀 깊이 제한을 10^6으로 하면 메모리 초과가 난다. import sys sys.setrecursionlimit(100000) input = s.. 2023. 4. 2.
[백준/BOJ] - 13265번 python 풀이 - bfs import sys from collections import deque def bfs(x): queue = deque([x]) color[x] = 1 #맨 처음 값 1로 칠하기 point = 2 #컬러 변수 while queue: v = queue.popleft() if color[v] == 1: point = 2 else: point = 1 for i in graph[v]: if color[i] == 0: #방문 안했다면 color[i] = point #point로 색칠 queue.append(i) else: #방문 했다면 if color[v] == color[i]: #색이 같아 버리면 return True T = int(input()) for i in range(T): n,m = map(int,in.. 2023. 3. 27.
[백준/BOJ] - 5014번 python 풀이 - bfs 1. 맨 처음 queue에 시작하는 층을 넣어준다. 2. 방문처리를 한다. 3. 큐에 값이 존재한다면 큐에서 값을 꺼낸다. 4. 꺼낸 값을 기준으로 up, down 값을 연산하여 방문처리, 카운트값 연산, 해당 값을 queue에 넣어준다. 5. 그러면 갈 수 있는 층의 count 값이 몇번 버튼을 눌러야 갈 수 있는 층인지 확인이 가능하다. import sys from collections import deque input = sys.stdin.readline #전체, 현재, 목적지, 업, 다운 f,s,g,u,d = map(int,input().split()) #경우의 수 방문처리 리스트 ok = [False] * (f+1) count = [0 for _ in range(f+1)] def bfs(): q.. 2023. 3. 27.
[백준/BOJ] - 2251번 python 풀이 - bfs 위 문제는 DFS,BFS 모두 가능한데 BFS로 풀었다. 1. 물통 크기를 각각 a, b, c로 설정한다. 2. 각 물통에 있는 물의 크기를 x, y, z로 설정한다. 3. x, y, z 각각의 경우의 수를 방문처리 하려고 직관적으로 접근하면 3차원 배열을 만들어야 하므로 4. x, y 물의 양으로 z를 도출할 수 있는 점을 이용하여 x, y만을 가지고 로직을 구성하였다. z = c(돌고도는 총 물의 양) - x(현재 a의 물의 양) - y(현재 b의 물의 양) 문제 조건에 의해 a 물통이 비었을 경우 c 물통에 있는 물의 크기를 구해야 하므로 queue를 돌며 a가 비었을 경우의 c물통에 있는 물의 크기를 answer에 추가한다. 경우의 수는 총 6가지 x → y x → z y → x y → z z →.. 2023. 3. 21.
[백준/BOJ] - 24230번 python 풀이 - dfs https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 색을 칠하면 자식 노드들이 모두 색칠해진다. 0은 디폴트 값이다. (하얀색) 노드들 사이의 관계 매핑시에 양방향 매핑 필요. dfs 탐색을 위한 반복문 부분에서 0이 아닌 부분(하얀색이 아니고)이고 방문 처리 되지 않았을 경우 dfs 탐색 시작. - color list는 [0]에 대한 빈값 처리를 해주지 않았기에 color[i-1] dfs 함수에선 연결된 노드들을 탐색 시도하고 연결된 노.. 2023. 3. 15.
728x90

티스토리툴바