Door

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 이 문제는 까다로운 지점이 많습니다. 우선, 그림으로 이 문제에서 봐야할 걸 보겠습니다. 바로 방문한 곳을 다시 갈 수 있는 점입니다. 조건에 불켜진 곳만 방문할 수 있다고 적혀있습니다. 그래서 처음에는 가지 못하는 곳이 다른 곳을 방문하면서 스위치를 키면 방문이 가능해집니다. 그런데 bfs를 구현하다보면 '한번 방문한 곳은 다시 방문하지 않는..

알고리즘 공부 2022. 9. 19. 14:20

https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 그래프+bfs에 대한 개념이 있으면 풀 수 있는 문제. 시작->도착 도착->시작 두 사이의 bfs를 구해서 이동거리를 구하면 됩니다. 그런데, 이 문제에서 구현해야 할 것이 하나 있습니다. 바로 '이미 갔던 지점은 가지 않는다'라는 조건. 시작->도착에서 갔던 지점은 도착->시작에서는 갈 수 없습니다. 예를들면 1,2,3,4,5 까지 길이 있고 1->3까지 간다고 ..

알고리즘 공부 2022. 9. 19. 09:53

https://www.acmicpc.net/problem/1724 1724번: 그림판 첫 행에는 그림판의 세로 방향 크기 N과 가로 방향 크기 M이 공백으로 구분되어 주어진다. (1

알고리즘 공부 2022. 9. 18. 13:31

https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제는 워낙 심플한데 풀이는 심플하지 않았던 문제. 제가 처음 틀렸던 풀이를 먼저 보겠습니다. #백준 1981 배열에서 이동 #틀린풀이 from heapq import heappop,heappush from copy import deepcopy dx=[0,0,1,-1] dy=[1,-1,0,0] N=int(input()) room=[] ma_val=0 mi_val=1e9 fo..

알고리즘 공부 2022. 9. 18. 11:42

https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 문제를 보면 당황스럽지만 하나씩 접근해보면 괜찮은 문제. 주의사항을 말하면 M과 Z 둘 중 하나는 움직여야합니다. M을 기준으로 움직인다했을때 M 근처의 파이프가 사라져서 M이 움직이지 못하는 경우가 생겨서 M이 움직이지 못합니다. 그러니 M과 Z 둘 중 하나를 움직이도록 설정해주세요. 움직이고 나서 끊어진 좌표가 있습니다. 그 해당 좌표가 바로 M과 Z사이를 잇는 좌표죠. 그 다음에는 동서남북으로 해당 좌표기준으로 어떤 트랙이 있는지 구합니다. 예를들면 해당 트렉근처로 남과 북에 길이 있다면 | 도로가 있으면 되고 동 북에 길이 있다면 2를 반환하면 됩니다. (이 부분은 구글링으로 힌트를 ..

알고리즘 공부 2022. 9. 17. 22:16

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 상당히 까다로운 문제 중 하나입니다. 다리를 넣고 어떻게 최소 경로를 만들어야하는지에 대해서 상당히 머리가 아픈 문제입니다. 우선, 구역을 나누는 건 bfs로 해주면 됩니다. 이렇게 구역나눠주는 건 할만합니다. 그 다음에는 다리 만들어주기. 다리를 만드는 조건은 '일자형'입니다. 방향을 중간에 바꾸면 안됩니다. 쭉~~한 방향으로 만. 다리를 만들어준 다음에는 '가장 짧은 다리..

알고리즘 공부 2022. 9. 16. 10:12

https://www.acmicpc.net/problem/16441 16441번: 아기돼지와 늑대 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열 www.acmicpc.net 2022.04.07 - [알고리즘 공부] - [백준 13460번] 구슬탈출 2(파이썬) [백준 13460번] 구슬탈출 2(파이썬) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양..

알고리즘 공부 2022. 9. 15. 10:54

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 이 문제는 '사이클'을 찾는 문제. 이 문제를 풀 때 처음에 드는 생각은 '시작점이 다시 만나면 사이클로 본다' 입니다. 그런데, 이렇게 생각하면 이런 반례가 생깁니다. 이렇게 사이클이 완성은 되는데 시작점으로 돌아오지 않는 케이스도 생깁니다. 이 부분까지 고려해서 수정했던 코드입니다. #백준 16724번 피리부는 사나이 N,M=map(int,input().sp..

알고리즘 공부 2022. 9. 14. 13:07