Door

https://www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 문제의 설명이 상당히 불친절한 문제입니다. 구글링의 코드를 참고하고서야 문제설명을 제대로 이해했습니다. 이 문제에서 포인트 몇가지 집어드리겠습니다. 1. 빈칸에 오작교를 설치할 수 있는 경우 -->0이 교차하는 지점을 제외합니다. 주변에 이미 놓여있는 오작교가 있는 거랑 무관합니다. (저는 주변에 오작교가 있으면 넣지 못하는 줄 알고 풀었으나 예시코드를 보니 아니었습니다.) 2. 오작교를 연속..

알고리즘 공부 2022. 8. 28. 18:09

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net bfs를 쓰는 건 알겠는데... 이 문제에서 생각이 잘 안났던 부분은 'Si칸만큼 이동한다'입니다. 보통 bfs쓰면 범위까지 계속 탐색하는데 이동할 수 있는 칸이 정해져있다고?? #백준 16920번 확장게임 from collections import deque import sys sys.setrecursionlimit(10**5) dx=[0,0,1,-1] dy=[1,-1,0,0] N,M,P=ma..

알고리즘 공부 2022. 8. 27. 23:51

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