너비우선탐색14 [BOJ] 1938. 통나무 옮기기(Python) / BFS 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 2021. 4. 11. [BOJ] 1525. 퍼즐(Python) / BFS 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 신박한 느낌의 BFS 문제였다. 처음 문제 봤을 때 감조차 잡히지 않았다. 이게 어떻게 BFS 인지 이해가 되지 않아, 코드 말고 아이디어 만이라도 얻어야겠다 싶어 구글링 해보니.. 3*3 맵에 있는 숫자들을 문자열로 변환해서 0이 있는 곳 기준으로 숫자 바꿀 수 있는 위치로 바꿔주고 BFS로 뻗어나가며 타겟 문자열을 찾는 방식으로 접근해야 한다는 것을 깨달았다. 이 아이디어를 바탕으로 코드를 짜봤다. # 아이디어 참고까지 30분, 문제 pass까지 1시간 30분/ 총 2시간 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 3*3 맵의 .. 2021. 4. 11. [BOJ] 11967. 불 켜기(Python) / BFS 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 각 방에서 불을 켤 수 있는 곳의 위치가 주어지면 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 불을 켤 수 있는 방의 최대 개수를 구하는 문제이다. 사용 알고리즘 : BFS 너비 우선 탐색 근래 풀어본 BFS 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 .. 2021. 4. 9. [BOJ] 2234. 성곽(Python) / BFS 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net # 1시간 40분 소요 사용 알고리즘 : BFS 너비 우선 탐색 문제 푸는 흐름은 아래 코드에 주석으로 잘 적어놨고, makeBinInfo() 함수 binInfo 딕셔너리에 0~16 숫자를 4자리 이진수로 변환한 정보를 담아줬다.(0: 나갈 수 있음, 1: 벽. 나갈 수 없음) checkRooms() 함수 visited 배열에 방의 번호를 적으며 bfs를 퍼트렸다. 이 때, 방 번호를 binInfo라는 딕셔너리를 활용해 현재 내 번호에 해당하는 남, 동, .. 2021. 4. 9. [BOJ] 6593. 상범 빌딩(Python) / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함 # 1시간 15분 소요 사용 알고리즘 : BFS 최단 거리 구하기 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다. Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순.. 2021. 4. 7. [BOJ] 2151. 거울 설치(Python) / BFS 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 하.. 이 문제는 일주일 동안 나를 괴롭혔기에 더욱 각별하다.. 정말 많이 고민 했는데 답 보기가 너무 자존심 상해서 끝까지 답을 안 보고 혼자 고민했다. 길을 걸을 때나 샤워할 때나 자기 전에나 계속 머릿 속으로 문제 푸는 그런 거.. 다들 경험 있으리라 생각한다. 이틀에 한 번 정도 풀어서 제출하고 틀리고를 반복하다 오늘 뭔가 다시 풀어보자! 해서 풀었는데 역시나 제출하자마자 "틀렸습니다"를 받았다. 질문 게시판에 있는 반례를 모두 넣어보며 내 .. 2021. 4. 5. 이전 1 2 3 다음
