Door

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

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