o_onn5

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제 보고 어떻게 해야할지 막막했다. 바이러스를 막을 최적의 벽 3개를 어떻게 알아내지????? 근데 그런 걱정을 하는 문제가 아니었다. 입력 조건을 보면 그래프 크기 최대가 8*8 이다ㅋㅋㅋ 그냥 벽을 세울 수 있는 모든 경우의 수를 구하면 되는 문제. 나는 아래와 같이 풀었다. (안전 영역 = 그래프 크기 - 바이러스 개수 - 벽 개수) BFS로 풀었고, 모든 경우의 수를 알기 위해서 itertoo..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 간단한 BFS 문제다. 큐에는 (현재위치, 주사위를 굴린 횟수)를 저장한다. 쉬운 문제라고 생각한다. 작년까지만 해도 실버 문제만 주구장창 풀었는데 알고리즘을 본격적으로 배운 이후 지금은 골드도 무섭지 않다. 물론 골드 중에도 못푸는 문제는 널리고 널렸지만 그래도 예전처럼 쫄아서 넘기진 않으니ㅋㅋㅋㅋㅋ 지금은 플래 문제들이 큰 벽처럼 보이지만 이것도 ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 전체적인 로직은 다른 사람들도 쉽게 잡았을거라고 생각한다. 그래서 쉽게 풀 수 있을 것이라 생각했는데 풀고 제출하니 시간초과;; 알고리즘은 다음과 같다 0. 벽으로 둘러싸인 빈 공간을 하나의 구역으로 취급한다. 1. BFS를 통해 각 구역의 빈 칸 개수를 따로 저장한다. (난 area 딕셔너리에 저장했다.) 2. 방문 처리를 위한 visited에는 구역의 번호를 저장한다. 3..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 많은 사람들이 DFS로 풀었는데 나는 BFS가 편해서 BFS로 풀었다. 처음에 deque로 접근하려 했다가 시간초과를 당했다. 자료구조 선택을 잘못했다. deque가 아닌 set으로 풀어야 통과가 됐다. deque로 풀게 되면 탐색 시간 복잡도가 O(n)이지만, set으로 풀면 O(1)이다. 일반적인 BFS처럼 visited 배열을 따로 만들지 않고 단순 문자열로 방문 처리를 해주면 된다...

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬이 겹쳤을 때가 관건인 문제였다.(이거 고민하느라 오래걸려서...) BFS는 둘째치고 시뮬레이션 너무 복잡한 것 같다. 삼성 SW 역량 테스트 문제라는데ㅋㅋㅋㅋ... 어려웠다ㅜ from collections import deque n,m = map(int,input().split()) board = [list(map(str, input())) ..