백준

[py3] 백준 2573 풀이 (빙산, DFS, 그래프)

이 문제는 일반적인 그래프에서 집합 개수 찾는 것과 시간마다 달라지는 그래프를 적용하여 푸는 문제이다. 여기서 중요하다고 느낀점은 빙하가 물과 닿는 개수대로 빙하가 녹게 되는데 녹일때 조심해야한다. 예를 들어 0 0 0 0 3 5 0 0 0 이라고 한다면 내년에는 0 0 0 0 0 3 0 0 0 이 되어야한다. 그러나 코드를 잘못짜면 0 0 0 0 0 2 0 0 0 이 될수 있다. 그래서 나는 filter 배열을 만들고 빙하별로 인접한 방향의 수를 구하고 제거하는 방식으로 코드를 구현했다. n,m = map(int , input().split()) M = [] big = 0 for _ in range(n): tmp = list(map(int, input().split())) M.append(tmp) fr..

백준 3055 C++ 풀이 (탈출, BFS)

이번에는 c++로 BFS문제를 풀어보자. 사실 엄청 어렵지는 않은 문제였다. 알고리즘을 어떻게 사용해서 풀지 쉽게 이해할 수 있었다. 그러나 문제는 c++!!!!! 맨날 파이썬으로 풀다가 c++을 접했더니 아주 신경써야할 게 한 두개가 아니다. 괜히 알고리즘 고수들의 언어가 아니었다. 준나 어렵다. 문제는 간단하다. 귀여운 고슴도치가 비버굴로 피난을 가는데 걸리는 시간을 구한다. 단, 물이 넘치게 되는 조건이 있는데 시간이 갈수록 물이 주변 지역으로 퍼진다. 이를 피하며 굴로 이동하면 된다. 가장 빠른 길을 찾는 것이기 때문에 BFS를 선택하면 된다. 또한 고슴도치는 물이 넘치는 지역으로 이동하면 안되기 때문에 물을 먼저 이동시키고 고슴도치를 이동시키면 된다. 1. 땅굴의 위치, 물의 위치, 고슴도치의 ..

백준 10026 파이썬 풀이 (적록색약, DFS)

이번 문제는 간단하다. 그냥 같은 영역이 얼마나 되는지 찾아내는 것이다. 1. 일반인을 위한 Map, 적록색약인 사람을 위한 Map('G'와 'R'를 동일하게 보는 사람) 2. DFS를 유연하게 만들어서 시간을 줄인다. n = int(input()) NMap = [] WMap = [] for i in range(n): tmp = list(input()) NMap.append(list(tmp)) for j in range(n): if tmp[j] == "G": tmp[j] = "R" WMap.append(tmp) def DFS(x,y, Map): s = [(x,y,Map[x][y])] Map[x][y] = 0 dx = [0,0,1,-1] #동서남북 dy = [1,-1,0,0] while s: x,y,z =..

백준 2583 파이썬 풀이 (영역 구하기, DFS)

이번 문제는 주어진 좌표만큼 색칠된 경우 색칠되지 않은 영역의 넓이와 개수를 구하면 된다. 1. 좌표를 배열위치로 바꾸기 2. DFS로 탐색하면서 넓이 구하기 이 두가지만 하면된다. 좌표는 그림을 그려서 구해보면 쉽게 확인가능하다. start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] 로 바꾸면 된다. 그럼 DFS로 탐색하는 코드만 추가해주면 끝이다. m,n,k = map(int, input().split()) Map = [[0 for i in range(n)] for i in range(m)] for _ in range(k): a,b,c,d = map(int, input().split()) start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] for i..

백준 1987 파이썬 풀이 (알파벳, DFS)

기존에 DFS,BFS문제는 주어진 미로에서 가장 짧은 길을 찾거나 걸리는 시간을 주로 구했다. 그런데 이번 문제는 미로가 아닌 각 칸에 알파벳이 주어질때 가장 멀리까지 가는 경우 몇칸이나 지나갈 수 있는지 구하는 것이다. 기존과 달리 모든 경우를 살펴보아야 구할 수 있다. 1. DFS로 각 칸은 상하좌우 확인한다. 2. 이때까지 지나온 알파벳과 중복되지 않으면 갈 수 있다.(즉, 해당 경로 혹은 지나왔는지 체크가 되어 있어야 한다.) 이렇게 2가지 조건을 통해 코딩을 진행했다. r, c = map(int, input().split()) M = [] for i in range(r): tmp = list(input()) M.append(tmp) alpha = [0]*26 alpha[ord(M[0][0])-6..

백준 2206 파이썬 풀이 (BFS, 벽 부수고 이동하기, 이차 배열 사용)

이 문제는 정말 나를 못살게 괴롭히는 놈이었다. 배열을 어떻게 해야할지 어떤 기준으로 visited를 하게 할지 굉장히 고민을 많이 하게 만들었다. 3차원 배열로 풀으라는데 내 방식대로 풀기 위해 상당히 고생을 했다. 우선 경우를 나누어본다. 벽을 뿌수고 이동하는 경우에는 다양하게 길이 갈리게 된다. 따라서 이미 누군가 지나간 길에 대해서 계속 갈지 말지를 정해야한다. 편의상 플레이어(경로를 가는 포인트)와 스킬(벽을 부쉈는지 아닌지)이라고 하겠다. 그렇다면 4가지 경우로 나눈다. 1. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓰지 않은 플레이어가 마주쳤을때 => 더이상 진행할 이유가 없다. 왜냐면 앞선 플레이어가 더 효율적 2. 스킬을 쓰지 않은 플레이어가 지나간 자리를 스킬을 쓴 플레이어가 ..

백준 7562 python 풀이 (나이트의 이동, BFS, 그래프)

문제는 나이트가 위와 같이 움직일 수 있을때 몇번 움직이면 원하는 목적지에 도달하는지 구하는 문제이다. 이전에 BFS문제와 아주 유사하다. 다만 그전에는 한칸씩 상하좌우로 움직였지만 이번에는 좀더 여러방면으로 움직이는 차이가 있다. 이때 가장 적은 움직임의 수를 구해야 하기 때문에 DFS가 아닌 BFS로 풀면 된다. 1. BFS를 구현 2. 좌표의 움직임을 구현 3. 이미 움직이거나 움직일 곳은 표시하여 중복을 제거 이를 토대로 코드를 구현하면 아래와 같다. from collections import deque T = int(input()) def BFS(l, start, end): M = [[0 for i in range(l)] for i in range(l)] M[start[0]][start[1]] ..

백준 7569 토마토 (BFS, 3차원)

이번 문제는 저번 7576문제를 3차원으로 바꾼 문제이다. https://guccin.tistory.com/92 백준 7576 토마토 (BFS, 행렬 그래프, python) 이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보 guccin.tistory.com 조건은 똑같다. 하루마다 양 사이드의 토마토가 익어가는데 추가되는 조건은 위아래 상자도 같이 적용된다는 것이다. 대충 3차원으로 생각해보고 위아래 같이 익게하는 조건을 추가하면 끝이다. from collections import deque m,n,h = map(int, input().split()) #열 행 상자수 q ..