[Python/파이썬] 백준 11559 - Puyo Puyo (뿌요 뿌요)

문제 설명 입출력 예제 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 코드 bfs 알고리즘 문제 분류에 있는 문제였지만 구현에 가까운 문제였다. 구현문제 답게 문제의 요구사항에 맞게 구현하여 풀 수 있었다. 이 문제에서 필요한 기능은 상하좌우 동일한 블록 탐색, 블록 제거, 블록 떨어트리기 총 3가지로 해당 기능들을 메서드로 뽑아 코드를 작성했다. 아래의 코드 주석을 통해 문제를 쉽게 이해할 수 있을 것이라고 생각한다. 정답 코드 from collections import deq..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 14.
• textsms

[Python/파이썬] 백준 17142 - 연구소3

문제 설명 입력과 출력 입출력 예제 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 풀이 코드 이 문제는 삼성 SW 기출문제에 출제된 문제라고 한다. 삼성 SW 문제들이 좀 문제를 이해하는데 어렵지 않나 한다. 이문제도 마찬가지로 문제를 이해하기가 좀 어려웠다; 이 문제를 푸는 방식에 대해 설명하자면 바이러스 M개를 활성화 해야하므로 파이썬의 combinations를 이용해 활성화할 바이러스 M개의 위치의 조합들을 구하여 해당 좌표들을 큐에 넣고 탐색하도록 하였다. 그리고 그 활성화된 바이러스 좌표들을 시작으로 빈칸 ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 13.
• textsms

[Python/파이썬] 백준 1600번 - 말이 되고픈 원숭이

문제 설명 입출력 예제 풀이 코드 이 문제는 2차원 배열이 아닌 3차원 배열 방식으로 풀어야 한다. 내가 3차원 배열로 표현한 방식은 visited[행][열][말처럼 움직일 수 있는 남은수(K)] 이다. 최소한의 동작으로 도착지점에 도착하기 위해서는 k번 말 처럼 움직인 다음 원숭이처럼 움직여야 최소한의 동작으로 도착 가능하다. 정답 코드 from collections import deque import sys input = sys.stdin.readline K = int(input()) W, H = map(int, input().split()) # 열, 행 board = [list(map(int, input().split())) for _ in range(H)] # 말처럼 이동하는 경우 dx_knigh..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 7.
• textsms

[Python/파이썬] 백준 2638번 - 치즈

문제 설명 입력과 출력 및 예제 풀이 코드 2차원 배열의 값들을 하나씩 탐색해 해당 부분이 외부 공기와 2번 이상 접촉했는지 확인해야 하므로 BFS를 이용해 문제를 풀 수 있다. 내 코드에서 주의할점으로는 치즈가 있는 부분은 visited 방문 처리 하지 않았다는 점인데 여러 면에서 공기와 접촉이 될 수 도 있기 때문에 이 부분을 방문 처리 해버리게 되면 해당 치즈는 무조건 한 면만 접촉되는 것이 되기 때문이다. 나머지 부분은 주석을 통해 이해할 수 있을 것으로 생각되어 자세한 설명은 생략한다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) cheeze = [l..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 4.
• textsms

[Python/파이썬] 백준 16928 - 뱀과 사다리 게임

문제 설명 입출력 예제 풀이 코드 10 x 10 크기의 보드판에서 진행되는 게임이라고 했지만 상하좌우로 움직이는게 아닌, 한 방향으로만 움직일 수 있다. 그렇기 대문에 2차원 배열이 아닌 1차원 배열로 나열해 풀 수 있다. 그리고 주어진 사다리, 뱀의 위치를 dict(딕셔너리) 타입으로 받아 주사위를 던져 도착한곳이 사다리, 뱀 위치(key)면 value로 이동시킨다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) # 사다리 수, 뱀 수 board = [0] * 101 visited = [False] * 101 ladder = dict() for _ in ran..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 26.
• textsms

[Python/파이썬] 백준 9019 - DSLR

문제 설명 입출력 예제 풀이 코드 A와 B는 모두 0 이상 10000이하의 수라고 했으므로 visited 배열의 수를 10000으로 초기화 해주었다. 그리고 방문하지 않은 수는 bfs 탐색을 시작한다. 여기서 핵심은 일반적인 bfs 문제의 dx, dy 상하좌우 이동 처럼 D, S, L, R 을 활용하는 것이다. 큰 난이도가 있는 문제는 아니라서 아래 코드와 주석을 참고하면 이해될 것이다. 참고로 테스트 케이스 반복문 때문인지 파이썬으로 제출하면 시간초과가 났고 PYPY3로 제출하니 통과할 수 있었다. 정답 코드 from collections import deque import sys input = sys.stdin.readline def applyCommand(n, command): if command ..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 6. 7.
• textsms