Door

https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 쉬운 bfs문제처럼 보이지만 '벽이 움직인다'라는 까다로운 조건이 붙어서 애를 많이 먹었습니다. 저는 처음에 while wall: wx,wy=wall.pop(0) nwx=wx+1 if nwx>=8: continue else: if [nwx,wy] in man: p=man.index([nwx,wy]) man.pop(p) room[nwx][wy]='#' new_wall.appen..

알고리즘 공부 2022. 7. 1. 15:52

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 이 문제에서 구현해야할 것은 크게 두 가지. 1. 빙산을 녹인다. 2. 빙산의 덩어리를 찾는다. 1. 빙산을 녹인다. 인접한 공간에 0이 있는지 확인하고 0이 있다면 -1 단, 빙산은 0에서 더 이상 뺼 수 없습니다. 이런 류의 문제는 deepcopy를 써주면 좋습니다. 만약 빙산을 받은 리스트에 0을 기준으로 지우다보면 위의 같은 NG케이스가 생깁니다. 원래는 0이 인접한 게 2개였는데 앞..

알고리즘 공부 2022. 6. 30. 15:29

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2022.06.22 - [알고리즘 공부] - [백준 7576] 토마토(파이썬) [백준 7576] 토마토(파이썬) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다... d..

알고리즘 공부 2022. 6. 30. 13:54

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS를 이용한 풀이입니다. 이런 유형의 문제는 풀이방법을 모른다면 체감난이도가 확 올라갈 수 있습니다. 그 이유는 '최소일수'를 구하는 것 때문이죠. 이 문제를 BFS로 푼다, 아니면 하다못해 DFS로 푼다는 것까지는 문제 유형을 읽다보면 생각이 어느정도 납니다. '토마토가 익을 때는 인접한 왼쪽 오른쪽만 익히는 구나. 그럼 토마토가 익는 걸 기점으로 그래프를 이동시키면..

알고리즘 공부 2022. 6. 22. 10:56

https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 이 문제는 아주 간단한 구현문제입니다. 처음에 다소 당황할 수 있겠지만 차근차근 풀다보면 풀어낼 수 있습니다. 소의 번호는 1~10까지 자연수이므로 저는 배열의 크기를 11로 선언했습니다. 배열은 0부터 들어가기 때무넹 11을 선언해서 0~10까지 선언이 됩니다. 어처피 맨 앞에 0은 안써도 되니 신경안써도 되고요. 저는 배열을 초기화할 때 -1로 초기화해줬습니다. 위치가 0,1로 이루어져있기 때..

알고리즘 공부 2022. 6. 7. 11:35

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 이 문제같은 경우에는 간단하게 deque의 rotate함수를 활용하는 방식이 있습니다만 공부의 관점에서 빡구현을 해봤습니다. 이 문제가 요구하는 사항은 다음과 같습니다. 1. 컨베이어벨트와 로봇을 돌린다. 2. 로봇을 이동 3. 새로운 로봇 투입 이 세가지를 반복해주는 작업을 겨쳐줍니다. 먼저, 컨베이어 밸트를 옮겨주는 작업, 여기서 end는 2*N입니다. #1.밸트위의 로봇..

알고리즘 공부 2022. 4. 24. 15:52

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제는 DFS로도 풀수는 있지만 일반적인 경우에는 시간초과가 발생합니다. 사실상 이 문제는 combination을 쓰라고 거의 유도한 문제에 가깝습니다. #백준 14899번 스타트와 링크 from itertools import combinations N=int(input()) graph=[list(map(int,input().split())) for _ in range(N)] numbers=[i for i in r..

알고리즘 공부 2022. 4. 24. 12:21

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 난이도 대비 정답률은 높았던 문제. 아마 널리 알려진 기출이라 '풀이보고 적어서 내야지' 하는 사람이 많았나...하는 예상이 듭니다만... 이 문제가 풀려있고 정답률도 60%대이길래 어 겁나 쉬운가보구나... 했더니 낑낑댔습니다. 문제 난이도 확인했더니 골드2.... 이 문제에서 구해줘야할 것은 다음과 같습니다. 1. 상어가 물고기 먹기 2. 물고기 이동 3. 상어가 이동 ; 여..

알고리즘 공부 2022. 4. 23. 23:40