Altiora Petamus

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🤔생각해보기 처음 떠올린 방법은, visited 와 똑같은 crashed 라는 배열을 만들어놓고 벽을 뚫었을 때 체크하는 방법과 3차원 배열을 활용해서 풀어보는 방법이다. 개인적으로는 2차원 배열도 머리가 복잡해져서 꺼리게 되는지라 3차원 배열 활용은 뒤로 미루고 crashed 라는 새로운 배열을 만들어놓고 활용해보려 했는데, 잘 안풀리고 오히려 더 복잡해져서 결국 1시간이나 더 써서 3차원 배열로 풀었다. (처음부터 그냥 곱게 3차원 ..

코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 🤔생각해보기 처음엔 문제를 보고 살짝 당황했다. 문자를 하나하나 모두 체크하라는건지 도대체 이걸 어떻게 풀어야하나... 그래서 그림으로 그려봤다. 이런 모양의 그래프가 그려지며, 그림을 보면 반대편 끝에 있는 "cog" 가지 도달하기 위한 깊이를 세어주면 되겠다는 느낌이 든다. 그래프를 그려보면 알게되지만, 결국 모든 스펠링의 검사가 필요하다. 알고리즘을 순서대로 적어보자면, 거리를 알기 위해 BFS 를 이용하여 각 노..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 🤔생각해보기 지금까지 시작 지점이 하나인 그래프 탐색은 비교적 간단하게 해결할 수 있었다. 하지만 이 문제는 동시에 여러 지점에서 탐색을 진행해야해서 어떻게 해야할까 고민이였는데, 잘 생각해보니 그냥 BFS 알고리즘에다가 시작지점만 여러개를 넣어주면 되는 것이였다. 익은 토마토의 좌표를 찾아서 root 배열에 담아놓는다. BFS 탐색을 위해 queue 에 root 들을 담은 상태로 초기화한다. 미로 탐색 과정을 응용해서 전 칸의 값에 1을 증가시..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🤔생각해보기 DFS와 BFS의 기본 개념을 익히기 위한 문제다. 자바에서는 2차원 배열로 edge 들을 설정한 뒤에 해결했었는데 파이썬에서 딕셔너리를 활용하여 풀어보았다. 개인적으로는 2차원 배열이 가독성이 끔찍하다고 느껴져서인지 어려워하는 편인데 딕셔너리를 활용해보니 이해하기도 편하고 훨씬 쉽게 해결 할 수 있는 것 같다. 성공 코드 from collections import deque from collections imp..