Door

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 이 문제에서 구현해야할 것은 크게 2가지. 1. 지운 노드의 아래 자식 노드 전부 삭제. 2. 자식노드 판별 여부 이 문제를 처음 접할 때는 트리를 전부 구현해서 푸는 건가... 하고 생각이 들었습니다. 그래서 열심히 파이썬에서 트리를 구현한 걸 찾아봤으나 이 문제에 적용하기는 힘들었습니다. 그러다가, 이 문제의 힌트를 얻으면서 차근히 풀었습니다. 1. dfs를 이용해서 자식노드를 지운다. ..

알고리즘 공부 2022. 7. 6. 13:04

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 이 문제는 처음 문제를 쓱 읽으면 '뭐야. 문제 개쉬운데?' 라는 착각을 줍니다. 물론 예제를 푸는 정도 수준은 어렵지 않는 코드이지만 그렇게하면 시간초과가 뜰 것입니다. #백준 16932번 모양만들기 from collections import deque N,M=map(int,input().split()) room=[] zero=[] ones=[] for x in range(N): da..

알고리즘 공부 2022. 7. 4. 22:48

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제는 BFS를 해줄 것이 2가지입니다. 하나는 불이 퍼지는 것. 또 하나는 지훈이의 이동. 이 문제가 조금 애매하게 서술해서 어떤 걸 먼저 BFS해줘야할지 애매해서 질문글을 찾아보니 불을 먼저 BFS해주는 걸로 했습니다. #1. 불이 먼저 번짐 new_fire=deque() for x,y in fire: for d in range(4): nx=x+dx[d] ny=y+dy[d] ..

알고리즘 공부 2022. 7. 2. 17:54

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/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 이 문제에서 접근해야할 것은 크게 2가지입니다. 1. 배열을 외부만 돌려주는 걸 어떻게 할 것인가. 2. 밖에 큰 거 돌려주고 안에 작은 건 어떻게 돌려줄것인가. 예시 1의 경우로 본 경우. 먼저, 외부의 사격형을 돌려주고 그 다음 안의 사격형을 돌려줘야합니다. 1. 돌려주는 경우. 저는 좌 하 우 상으..

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