Door

https://www.acmicpc.net/problem/1400 1400번: 화물차 입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 2 www.acmicpc.net 이 문제는 억울함이 많았던...ㅠ 우선 처음에 생각했던 풀이는 '교차로를 만날 때 바로 신호등이 켜지는 경우와 신호가 켜지기 기다렸다가 건너는 케이스 두 가지를 구현한다' 였습니다. #백준 1400번 화물차 from heapq import heappop,heappush dx=[0,1,0,-1] dy=[1,0,-1,0] while True: m,n=map(int,input().split())..

알고리즘 공부 2022. 8. 31. 21:51

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 이 문제를 들었던 생각들. '통나무를 어떻게 옮기지???' 3개를 한번에 옮겨? 3개를 deque에 받고 옮겨? 이렇게 생각하니 문제가 전혀 안풀렸습니다. 그러다가 질문하기 글을 봤는데 의외로 간단한 해결책이 있었습니다. '중앙점을 중심으로 옮긴다' 중앙점 x,y를 기준으로 가로,세로인지 확인해주고 그걸 옮긴다는 개념이었습니다. 그렇게 머릿속에 박고 다시 시작하니 문제가 체..

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

https://www.acmicpc.net/problem/22949 22949번: 회전 미로 탐색 $4k$×$4k$의 크기인 미로가 있다. 이 미로의 최상단 왼쪽을 $(1, 1)$, 최하단 오른쪽을 $(4k, 4k)$로 하자. $\{(y, x) | 4×i < y ≤ 4×(i+1), 4×j < x ≤ 4×(j+1), (0 ≤ i, j < k)\}$ 를 만족하는 영역이 하나의 구역으 www.acmicpc.net 문제를 보자마자 이게 뭐지?? 하면서 당황했던 문제. 가장 문제에서 난감했던 부분은 '배열을 돌리고 해당 구역 이외에는 원상복귀시킨다' 구역이 계속 바뀐다고? 그러면 dfs로 풀어야하는거 아닌가? 구역을 계속 업데이트해주고... 하...이게 뭔 쌉소리지?? https://nahwasa.com/entr..

알고리즘 공부 2022. 8. 30. 11:03

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