그래프 탐색 (41) 썸네일형 리스트형 [Python] 20130번 Metroidvania Extreme https://www.acmicpc.net/problem/20130 20130번: Metroidvania Extreme 첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다. www.acmicpc.net 22/10/08 독특한 아이디어가 돋보이는 BFS문제로, 일반적인 BFS가 아니라 더 재미있게 느껴졌던 문제이다. 문제 접근 방식: 일단 당연히 시작 지점부터 무지성으로 BFS를 진행하면 안 된다. 해당 알파벳의 대문자 지점은 해당 알파벳의 소문자가 열쇠인데, 그 열쇠를 얻어야만 대문자 지역을 지날 수 있다는 제약조건이 걸려있기 때문이다. 이 문제의 핵심 아이디어는, 대문자 지역을 방문했을 때 열쇠를.. [Python] 7569번 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 22/09/30 이 문제는 7576번 토마토와 거의 유사한 문제로, 이 문제에서 3차원으로 바꾸기만 하면 되는 문제이다. https://lighter.tistory.com/34 [Python] 7576번 토마토 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자.. [Text] 22311번 Maze 6 https://www.acmicpc.net/problem/22311 22311번: Maze 6 In southern Ontario, many corn farmers create cornstalk mazes like the one shown. The mazes are created in the fall, after the grain has been harvested. There is still time for you to help design the best maze ever for 2010. A field is covered with corn st www.acmicpc.net 22/09/27 코드를 짜지 않고도 충분히 손으로도 풀 수 있는 문제로, 같은 시리즈의 Maze 9문제와 함께 풀면 더욱 좋은 문.. [Python] 9918번 Cube / 2642번 전개도 https://www.acmicpc.net/problem/9918 9918번: Cube Folding six squares connected in some special ways can form a cube. For example, in the diagram below, the six squares on the left can be folded into a cube (with face 1 opposite face 4, face 2 opposite face 6, and face 3 opposite face 5) but the six squ www.acmicpc.net https://www.acmicpc.net/problem/2642 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지.. [Python] 18126번 너구리 구구 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 22/09/19 그룹원들과 푼 그룹 주간 문제로 이 문제를 선택해서 풀었다. 오랜만에 DFS문제, 그것도 일반적인 matrix모양으로 간선이 주어지는 것이 아닌 실제 간선 모양으로 주어지는 그래프라서 조금 헷갈리긴 했지만 더듬더듬 기억을 되살려 가며 주석을 달아가며 작성했던 문제이다. 문제 접근 방식: 처음에는 이 문제를 재귀 오류로 틀렸었다. (재귀 제한 코드를 실수로 적지 못했다... [Python] 16113번 시그널 https://www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 www.acmicpc.net 22/09/14 좀 귀찮았던 문자열 겸 그래프 문제였다. 아이디어 자체는 매우 쉬웠으나 예외 처리하는 부분이 좀 있어서 구현이 귀찮았었다. 문제 접근 방식: 접근 자체는 매우 단순하게 접근했다. 기본적으로 1을 제외한 숫자는 가로 3칸 세로 5칸으로 이루어져 있고, 우리는 숫자를 알아내고 싶다. 따라서 입력받은 문자열을 세로 5칸이 되도록 쪼개서 행렬로 바꾸도록 구현했다.(첫번째 귀찮았.. [Python] 21938번 영상처리 https://www.acmicpc.net/problem/21938 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 22/09/13 오랜만에 풀어보는 그래프 탐색 문제여서 조금 맞왜틀을 많이 했던 문제이다. 지금 다시 보니 실수했던 부분이 많이 보인다. 이 문제를 2가지 방법으로 풀려고 해봤으나, BFS는 익숙하지 않아서 BFS로 해결하지 않았다. 문제 접근 방식: DFS로 접근하였다. 오랜만에 DFS코드를 짜는 것이어서 많이 틀리기도 하고 시간 초과, 메모리.. [Python] 3709번 레이저빔은 어디로 https://www.acmicpc.net/problem/3709 3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net 22/09/10 그룹 연습에서 풀었던 문제로, 시뮬레이션 문제를 오랜만에 풀어보는 터라 당황스러웠지만 재미있기도 했다. 문제 접근 방식: 특별한 알고리즘은 없고, 문제를 말 그대로 구현했다. 근데 보드를 딱 N*N크기로 구현한 것이 아니라, 그보다 위아래 왼쪽 오른쪽으로 1칸씩 크게 만들었다. 그 이유는 보드에서 레이저를 쏜다고 했으니, 그 레이저를 놓을 공간이 필요하다고 생각했기 때문이다. 우향.. 이전 1 2 3 4 5 6 다음
