Door

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 단순하게 각 좌표마다 bfs를 써서 이동한 다음에 미로를 빠져나가는지 확인하는 방식이 있지만 이 방식은 제출하자마자 시간초과가 뜹니다. 이 문제가 골드3인걸 생각하면 그렇게 단순할리가 없죠. 이 문제는 dp를 함께 사용하는 방식입니다. dp라고 해봤자, 해당 지점의 탈출여부를 판단하는 건데요. 만약에 위로 이동했을 때 좌표가 '나갈 수 있는 좌표'라는 표시가 있다면 굳이 더 나아가..

알고리즘 공부 2022. 8. 27. 16:07

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이 문제의 입력은 무조건 C와 C가 서로 연결되는 구조라는 가정이 있습니다. 이 문제는 거울을 어떻게 넣어줄건지 생각하면 되는 문제입니다. 다익스트라로 풀 수 있는데 한가지 주의할 포인트가 있습니다. (.은 0 *은 1 출발점은 f 도착점은 e) 이 그림의 □의 경우에는 여러 방향에서 오는 케이스가 존재합니다. 다익스트라 알고리즘을 쓰다가 이 부분을 놓쳐서 다소 해맸다가 수정했습니다. #..

알고리즘 공부 2022. 8. 27. 13:29

https://www.acmicpc.net/problem/3089 3089번: 네잎 클로버를 찾아서 숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 2차 www.acmicpc.net 이 문제는 구현방식은 간단한데 시간초과 관점에서 생각할 것이 많은 문제였습니다. #백준 3089번 네잎클로버를 찾아서 dx=[0,0,1,-1] dy=[-1,1,0,0] N,M=map(int,input().split()) clover=[] for _ in range(N): X,Y=map(int,input().split()) clover.append([Y,X]) command=input().rst..

알고리즘 공부 2022. 8. 26. 00:00

https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 이 문제는 가중치가 있기 때문에 다익스트라를 쓰면 좋습니다. 다만, 이 문제는 일반적인 BFS,DFS와 다른 점이 있습니다. 바로 '한번에 쭉 간다'라는 것. 테라는 미끄러지면서 이동합니다. 상하좌우로 미끄러질 수 있는데 돌이나 출구를 만나기 전까지 미끄러집니다. 만약 범위를 벗어나거나 구멍을 만나면 아웃이고요. 그래서 한번에 쭉~~~미끄러진다는 걸 구현만 한다면 이 문제는 상대적으로 무난한게 풀 수..

알고리즘 공부 2022. 8. 25. 17:25

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 이 문제는 풀이방법은 단순할 수 있지만 어떻게하면 반복문을 줄일 수 있는가에 대해서 생각해보면 좋은 문제입니다. 우선, 아래는 제가 처음 이 문제를 보자마자 바로 떠올린 코드입니다. #백준 10775번 공항 G=int(input()) P=int(input()) gate=[i for i in range(1,G+1)] g_in=[False]*(G+1) planes=[..

알고리즘 공부 2022. 8. 24. 15:28

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 처음 이 문제를 만났을 때에는 '이게 골드2? 이거 골드 5수준이잖아?' 하면서 쉽게 생각했습니다. 그리고 제출하자마자 시간초과. 제가 생각한 방식은 간단했습니다. '지도돌다가 1만나면 거기서 bfs해준다' 이렇게 하면 예제는 통과하지만 시간초과가 납니다. 그리고 시간초과가 뜰 때 내가 뭘 생각하지 못하는구나 깨닫고 힌트를 얻어봤습니다. https://ku-hug.tistor..

알고리즘 공부 2022. 8. 22. 12:02

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 알고리즘로직보다도 시간초과,메모리 초과와의 싸움을 해야하는게 무척이나 힘들었습니다. 이런 경로를 찾는 알고리즘은 다익스트라 알고리즘을 쓰면 쉽게 풀립니다. https://justkode.kr/algorithm/python-dijkstra Python으로 다익스트라(dijkstra) 알고리즘 구현하기 최단 경로 알고리즘은 지하철 노선도, 네비게이션 등 다방..

알고리즘 공부 2022. 8. 21. 19:10

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제는 BFS로 외부 공기를 계속 구해주면서 치즈를 제거하는 문제입니다. 2022.06.30 - [알고리즘 공부] - [백준 2573번] 빙산(파이썬) [백준 2573번] 빙산(파이썬) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진..

알고리즘 공부 2022. 8. 21. 11:52