본문 바로가기

분류 전체보기

 (249)
[BOJ] 13549. 숨바꼭질 3 문제 숨바꼭질 3 (https://www.acmicpc.net/problem/13549) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이전 12851. 숨바꼭질 2 문제에서 방법에 약간 변형을 준 것이다. 이전 문제에서는, 현재 위치 cur에서 다음 위치 cur-1, cur+1, cur*2 를 한번에 처리했다면, 이번엔 경우를 나눠야한다. 먼저, visited[cur] 는 cur 위치에 올 때 걸리는 최소 시간을 담는다. cur-1, cur+1 로 이동하는 경우, 현재 위치까지 걸린 시간 + 1 을 해준다. 즉, visited[cur-1], visited[cur+1] = visited[cur] + 1 이다. 이 때, 당연히 이..
[BOJ] 12851. 숨바꼭질 2 문제 숨바꼭질 2 (https://www.acmicpc.net/problem/12851) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이전 1697. 숨바꼭질 문제에서 경로의 갯수가 추가된 것이다. 이제 우리는 2가지를 생각해야 한다. 하나는, n 까지 오는데의 최소 시간(time) 과 이를 저장하는 방법 (visited[n]) 이고, 다른 하나는, n 까지 최소 시간으로 오는 방법의 수(ways[n])다. 어떤 좌표 j 가 있다고 하자. 이 좌표에 오는 방법에는 3가지 방법이 있을 것이다. (j-1,j+1, j/2 에서 온다.) 경우가 3가지 이므로, j에 오는 방법은 3가지 일까? 아니다. 우리는 최소 시간 을 고려해야 한..
[BOJ] 7569. 토마토 문제 토마토 (https://www.acmicpc.net/problem/7569) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 이전 7576. 토마토 문제에서 위아래 방향만 추가한 것이다. 코드 import sys from collections import deque dzs = [0, 0, 0, 0, 1, -1] dxs = [-1, 0, 1, 0, 0, 0] dys = [0, -1, 0, 1, 0, 0] m, n, h = map(int, sys.stdin.readline().split()) board, q, visited = [], deque(), set() for _ in range(..
[BOJ ]7576. 토마토 문제 토마토 (https://www.acmicpc.net/problem/7576) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 코드 import sys from collections import deque dxs = [-1, 0, 1, 0] dys = [0, -1, 0, 1] m, n = map(int, sys.stdin.readline().split()) board, q, visited = [], deque(), set() for _ in range(n): board.append(list(map(int, input().split()))) for i in range(n): for j i..
[BOJ] 2644. 촌수 계산 문제 촌수계산 (https://www.acmicpc.net/problem/2644) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 파이썬에서 그래프 탐색이 필요한 문제들은, 일단 dict {} 로 그래프를 먼저 만들고, (부모노드가 key, 자식노드들이 해당 key의 values가 된다.) set {} 으로 방문체크용 스트럭처를 만들면 된다. 이러면 노드접근에 모두 상수시간 O(1) 밖에 안걸린다. 코드 import sys from collections import defaultdict n = int(input()) a, b = map(int, input().split()) t = int..
[BOJ] 16397. 탈출 문제 숨바꼭질 (https://www.acmicpc.net/problem/1697) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 전체적으로 1697.숨바꼭질 과 동일한 문제다. 다만, 여기서 신경써야할 부분은, 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 이 부분이다. 언어에 따라 다르게 처리할 수 있겠지만, 파이썬은 그래도 str() 이나 int() , .join() 을 통해 쉽게 처리할 수 있다. 아래 코드를 보면 된다. 코드 import sys n, t, g = list(map(int, sys.stdin.readline().split())) def bfs(n, t, g): ..
[BOJ] 1697. 숨바꼭질 문제 숨바꼭질 (https://www.acmicpc.net/problem/1697) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이동 방향이 3가지로 정해져 있다. 목표지점이 정해져있으므로, 해당 목표지점에 도달 시, BFS를 끝내고, 지금까지 간선의 스텝(time) 을 반환한다. 우리는 모든 노드를 최대한 1번 방문하며 BFS를 진행한다. 따라서 시간 복잡도는 O(n) 이다. 맨 처음 생각엔, 한 스텝에서 갈 수 있는 경우의수가 3가지 이므로, n번 스텝까지 진행할 시, O(3^n) 이 아닌가 했다. 이는 매우 큰 수로, k가 좀만 커져도 1억을 넘어 시간초과다. BFS의 시간복잡도는 O(|V|+|E|) 로 알려져있다. 여기..
[BOJ] 9466. 텀 프로젝트 문제 텀 프로젝트 (https://www.acmicpc.net/problem/9466) 풀이 1. 초기접근 문제조건 해석 문제를 잘 읽어보면, 주어진 데이터를 그래프로 보고, 이 중, 싸이클 인 것만 한 팀이 되는 것을 알 수 있다. 즉, 주어진 학생의 수(노드) n개에서 싸이클이 아닌 학생(노드) 만 잡아내면 된다. 알고리즘 모든 노드를 순차적으로 탐색해야 하므로, 기본적으로 DFS 다. 간선을 따라 DFS를 진행하되, 다음 진행 노드가 이전에 방문된 적이 있다면 (visited), 그 노드부터 현재노드까지 싸이클 내에 있음을 알 수 있다. 위 방식으로, 싸이클을 발견했다면, DFS 를 종료하고, 다시 하나씩 반대방향으로 back 하며 cycle 내에 있는 노드는 팀을 이룬다는 체크를 해준다.(team..

티스토리툴바