본문 바로가기

코딩테스트166

[ 파이썬(python) ] 백준 1743 - 음식물피하기 (BFS) 📌 백준 1743 - 음식물 피하기 문제 설명 💡 나의 풀이 전형적인 BFS 혹은 DFS 문제이고, 입력에 음식물의 좌표를 입력받아 BFS, DFS를 돌려 단순 개수를 파악하고 기존 개수와 현재 개수를 비교하여 더 큰 값으로 갱신해주면 되는 방향으로 문제를 풀면 된다. 여기서 약간 까다로운 부분은 좌표를 직접 입력받는 부분일 텐데, 우리가 사용하는 graph는 0부터 시작하므로 입력을 받을 때 -1처리를 해주면 오류없이 그래프에 입력할 수 있다. 풀이 흐름을 직접 그려봤다. import sys from collections import deque input = sys.stdin.readline def bfs(x, y): cnt = 0 queue = deque() queue.append((x, y)) vi.. 2021. 4. 22.
[ 파이썬(python) ] 백준 1303 - 전쟁 - 전투(BFS) 📌 백준 1303 - 전쟁 - 전투 문제 설명 💡 나의 풀이 (여담이지만 1303 하니까 국방 헬프콜이 생각났다.) 2차원 배열에서 각 색깔에 맞는 거리를 구하는 전형적인 BFS문제이지만, 헷갈린 부분들이 많았다. 한쪽 BFS만 구하는것이 아니고 양쪽 BFS를 모두 구현해야하다보니까 함수를 어떻게 선언하는지 굉장히 고민을 많이 했다. 결론적으로 BFS 함수에 color라는 파라미터를 작성해서 넘겨줬고 함수내에서 각 칸의 거리를 구하는 방법은 각 색깔별로 w_cnt, b_cnt를 따로따로 선언하지 않고 cnt 변수 하나만 선언해서 색깔 별로 조건문을 다르게 주어 현재 들어온 색을 기준으로 cnt를 세고 return하는 방법으로 진행했다. 이 방법까지 캐치하는데 상당히 오랜 시간이 걸렸다. 어제 첫 알고리즘.. 2021. 4. 21.
[ 파이썬(python) ] 백준 4963 - 섬의 개수(DFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 2번을 사용하면 쉽게 해결 할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20.
[ 파이썬(python) ] 백준 4963 - 섬의 개수(BFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 패턴2를 사용하면 쉽게 해결할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20.
[ 파이썬(python) ] 백준 7576 - 토마토(BFS) 📌 백준 7576 - 토마토 문제 설명 💡 나의 풀이 나의 수준에서는 어려웠다... 익은 토마토가 1개일 경우에는 잘 구할 수 있었는데, 2개 이상인 경우는 도저히 생각이 나지 않았다. 그래서 다른사람의 코드를 조금 참고했는데 BFS를 동시에 2개를 돌리는 방법은 아예 생각도 못했고 그러다 보니까 함수의 코드도 이전에 풀던 방법과는 조금 달라서 고민하며 문제를 푸느라 반나절을 쏟아버렸다. 처음에 익은 토마토가 2개 이상 있을 때 케이스를 하나씩 더해서 두 개를 더해주면 될 줄 알았다. 컴퓨팅적으로 생각하지 않고 내키는 대로 생각해버려서 안 되는 방법으로 구현하려니까 머리가 꼬여버렸다. 그리고 문제 마지막에 모든 토마토가 익어있는 상태를 0으로 출력해야하는데, 이 경우는 제외하고 코드를 작성했다. 그래서 .. 2021. 4. 20.

티스토리툴바