https://www.acmicpc.net/problem/14868 문명은 전파된다고 한다. 문명이 전파되었을 때, 문명끼리 다 만나는 시점을 구하는 문제다. 단순히 생각해봤을 때, 문명이 전파하고 문명이 만난 것을 표현해주려면 현재 그래프에서 문명의 값을 설정해주고, 만날 때 마다 문명의 값을 흡수되는 쪽으로 다 바꿔주면 된다. 쉽게 얘기하면 위의 그림처럼 되면 된다. 1,2가 만나면 모든 2가 1로 바뀌는 것이다. 아주 단순한 방법이다. 그런데 이렇게 할 경우 큰 문제점이 생긴다. 바로 너무 비효율적이라는 것이다. 현재 문명은 20만개가 주어질 수 있다고 한다. 그리고 전체 맵은 2000 * 2000으로 4,000,000 칸을 보여준다. 맵에 모두 업데이트 한다고 하면 최악의 경우 4,..
https://www.acmicpc.net/problem/1473 1473번: 미로 탈출 세준이는 직사각형 모양의 미로에 갇혔다. 미로 안에는 1*1크기의 작은 방이 있다. 정사각형 모양의 각 방은 네 개의 면이 있는데, 이 네 개의 면에는 문이 있을수도 있고, 없을수도 있다. 각 방은 www.acmicpc.net 일단 스위치를 켜고 끄면 비트마스킹을 떠올리는 것이 가장 빠르다. 비트마스킹이 가능한지를 먼저 검토해봐야한다. 입력으로 들어올 수 있는 최대 크기는 49다. 각 행, 열은 총 7개씩 들어올 수 있다. 행, 열의 비트 상태를 나타낼 수 있는 배열은 각각 128(2^7)개다. 각 행마다 각 열의 비트 상태가 나열될 수 있으니 128 * 128이된다. 총 만들어지는 열은 128 * 128 * 4..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 원숭이는 말처럼 최대 30번까지만 움직일 수 있다. 가장 먼저 고려해야하는 것은 이것이다. 말처럼 움직여서 먼저 도착한 위치가 있다. 이 위치에 원숭이가 뒤늦게 도착하면, 이 모수는 더 이상 볼 필요가 없을까? 를 고민해야한다. 그런데 말처럼 먼저 도착했는데, 말의 횟수를 다 쓰고 다음은 말로 이동해야만 갈 수 있는 반례가 존재한다. 따라서 말처럼 움직이는 것과 원숭이처럼 움직이는..
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 시간을 줄이는데 피똥 싼 문제다. 처음에 접근한 방법은 내가 생각하기에는 BFS 단 2번에 처리할 수 있다고 생각해서 손쉽게 통과할 줄 알았는데 TLE가 났다. 왜 그런지는.. 나 혼자로는 어려워 백준 게시판에 문의 글을 적어두었다. 혹시나 누군가 답변을 달아주시면 공유를 해보려고 한다. 첫번째 접근한 방법은 다음과 같다. 얼음을 깰 수 있는만큼 깬다. 얼음을 ..
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 3차원 BFS를 할 수 있는지 묻는 문제다. Z축을 하나 더 추가해서 동일하게 BFS를 돌려주면 된다. 옛날 문제인데, 옛날 문제가 까다로운 부분은 입력을 처리하는 부분이다. 난 문제도 잘 못 풀긴 한데, 입력이 지저분하면 더욱 멘붕이다. import sys from collections import deque def bfs(sz,sr,sc, a,b,d,): # 변수 초기화 que = deque() q..