Door

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

https://www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다. 어떤 칸 www.acmicpc.net 이 문제는 어떻게 색을 칠할지 먼저 고려해야합니다. https://astrid-dm.tistory.com/380 백준 12946번 육각 보드 (C++) 문제 링크 : www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려..

알고리즘 공부 2022. 9. 14. 10:40

https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 이 문제는 삽질한 과정이 많아서 풀이를 전부 파보겠습니다. 우선 이 문제에서 구현해야할 것. 1. 나무로부터 거리 구하기 2. 최단경로 구하기 1번은 bfs를 써서 구하면 됩니다. 나무를 deque에 받고 bfs로 거리를 구하면 끝. 문제는 2번인데... 우선 처음에 틀렸던 풀이. #백준 2817번 늑대사냥꾼 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0..

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

https://www.acmicpc.net/problem/14947 14947번: 상자 배달 처음 지도의 세로 크기 n과 가로 크기 m이 주어진다(1 ≤ n ≤ 500, 1 ≤ m ≤ 500). 다음 n개의 줄에는 m개의 숫자가 주어진다. 0은 싱크홀이고 1은 땅, 2는 시작지점, 3은 목적지다. www.acmicpc.net 처음에는 중간점을 x,y로 두고 1x1 1x3나누는 건 생각했지만 1x3을 가로,세로로 구현하는 부분이 제대로 되지 않았습니다. 제대로 구현하기 위해서 state==0-->1x1 state==1-->1x3(가로) state==2-->1x3(세로) 이렇게 나눠서 상자가 움직일때를 구현했습니다. #백준 14947번 상자배달 from collections import deque dx=[0..

알고리즘 공부 2022. 9. 13. 11:40

https://www.acmicpc.net/problem/25208 25208번: 새벽의 탐정 게임 새벽의 탐정 게임은 재미있는 2인용 보드게임이다. 한 명은 탐정, 다른 한 명은 도둑 역할을 맡는다. 게임은 $N$행 $M$열 격자 위에서 진행된다. 격자의 각 칸은 벽이 설치되어 있거나 비어있고, 역 www.acmicpc.net 정육면체를 굴리면서 가야해서 체감난이도가 올라갔습니다. 도형굴리는 부분은 진짜 프로그래밍 삐긋~ 해버리면 답이 안나오는 유형이라 돌리는 거 구현하는 것만으로도 스트레스받네요. q에 cube를 받고 1을 바닥면으로 설정. 만약 x,y좌표에 도둑이 있고 cube[1]==1이라면 도둑을 잡은 것으로 설정. 이동하면서 조건에 맞게 cube를 돌려주면 됩니다. #백준 25208번 새벽의 ..

알고리즘 공부 2022. 9. 12. 11:00

https://www.acmicpc.net/problem/14948 14948번: 군대탈출하기 첫 줄에 각 병영의 세로 길이 n, 가로 길이 m 이 주어진다. (1 ≤ n, m ≤ 100) 다음 줄부터 차례대로 병영의 블록별 레벨 제한 k가 주어진다. (0 ≤ k ≤ 109). www.acmicpc.net 삽질을 참 많이 한 문제. 이 문제는 '도움닫기'입니다. bfs를 해주면서 '벽타고 넘기기'를 해주면 됩니다. 벽을 탈때에는 이동하는 방향 그대로 한번 더 이동해주면 됩니다. #백준 14948번 군대탈출하기 from heapq import heappop,heappush import sys dx=[0,0,1,-1] dy=[1,-1,0,0] N,M=map(int,input().split()) room=[l..

알고리즘 공부 2022. 9. 11. 20:10