Dalin's Archive

문제 풀러 가기!! 설명 🤔😊 조합 + 구현 + BFS로 풀었다 ㅎㅎ 벽을 꼭 3개 새로 세워야 한다.-> 어디에 세울까?? N, M이 최대 8이니까 최대 64칸이 나온다. 64칸 중에 3칸에 벽을 세우는 경우를 구한다. 즉 조합으로 어디에 벽을 새로 세울지 구했다. 이 경우들을 쭉~~ 봐줬다. 빈칸에만 새로 벽을 세울 수 있으니 빈칸인지 확인하고, 빈칸이면 벽을 세웠다. 벽을 세운 후, 바이러스가 퍼져나가는 걸 시뮬레이션했다. 이때 BFS를 사용했다. 마지막으로 빈 칸 수를 세고, 정답을 업데이트하면 된다! 코드 👏💖 import sys from itertools import combinations from collections import deque from copy import deepcopy in..

문제 풀러 가기!! 오 ㅎㅎ 재밌는 BFS 문제였다. 처음에는 어떻게 풀지 고민되어서 문제 분류를 봤다. BFS 라고 하니 감이 와서 풀 수 있었다! 보통 너비 우선 탐색을 하면 2차원 테이블 안에서 가장 빨리 도착하는 식으로 풀었는데, 직선 상에서 오리, 육리가 만나는 걸 찾아서 특이했다. 또 보통은 하나에서 출발해서 고정된 도착점을 찾는 식이었는데, 이번에는 오리, 육리가 둘 다 움직여서 독특했다. 오리, 육리가 만날 수 있는 최소 일수를 구해야 하므로 BFS를 사용했다. 1. 오리, 육리의 (점프 횟수, 위치, 이름)을 q에 넣었다. 2. q가 있는 동안 while문을 돌렸다. 2-1. q에 있는 원소를 popleft로 꺼냈다. (먼저 들어온 걸 먼저 꺼냄) 점프 횟수, 위치, 오리인지 육리인지가 ..

문제 보러 가기! 오랜만에 BFS를 풀어서 재미있었다~! 평범한 BFS 문제 + 빙판 부분이 특별했다. 먼저 늑대의 위치를 확인해서 리스트에 넣은 후에, 늑대 한 마리씩 확인했다. (늑대가 여럿 있을 수도 있음) 늑대가 방문할 수 있는 곳인지 방문 체크를 했다. (wolve_can_go 2차원 리스트) 빙판 부분은 while을 이용해서, 쭉~ 미끄러지듯 가줬다. 가고 있는 방향 쪽으로 한 칸 더 갔을 때(범위 확인 후) 빙판이면 한 번 더 가기 초원이라면 그만!(즉 늑대가 방문할 수 있다고 체크한 후, 큐에 넣었다.) 산이라면 그 이전 위치에서 멈추도록 했다. (멈춰서 다른 방향 갈 수 있기 때문이다! 처음에 이 부분을 안 처리해서 틀렸다. 그 이전 위치를 방문 체크한 후, 큐에 그 이전 위치를 넣았다...

문제 보러 가기! 평범한 BFS 문제에서 조금 더 생각해야 했다.. dq에는 위치, 얼마나 걸렸는지를 가지고 있는다. 앞으로 걷고, 뒤로 걷고, 순간이동하는 경우를 범위, 방문 체크한 후에 dq에 넣는다. 일단 N이 0일 때는 곱하기 2해도 0이고, -1은 해도 점점 멀어지는 거니까 괜히 시간만 든다. N이 0일 때는 일단 무조건 한 칸 앞으로 가야 하니까, dq에 (N+1, 1)을 넣고 시작한다. 틀리다가 질문 게시판의 반례!!를 보고 문제를 알았다. dq에 넣을 때 방문 체크를 하면 안되고, 뺄 때 방문 체크를 해야 한다! 1 10의 경우에 1->2->4->5->10으로 가는 게 젤 빨리 가는 것인데, 1에서 2로 갈 때 걸어서 갈 수도, 순간 이동해서 갈 수도 있다. dq에 넣을 때 방문 체크를 하..

문제 보러 가기 접근 BFS로 풀었다. 큐에서 단어를 꺼내면 -> 그 단어에서 토 달기 규칙을 지키면서 사전에 등재된 단어들을 큐 안에 넣어줬다. 이게 check 함수이다. 어떤 단어(target_word)가 들어오면, 사전을 쭉 ~ 본다. 그러면서 target_word에서 토달기를 했을 때 사전의 해당 단어가 될 수 있다면, 리스트에 넣었다. 일단 토달기는 한 글자만 더할 수 있으니까, 사전의 단어 길이가 target_word+1인지 봤다. 아니라면 continue. 그 다음에 토달기 방식 중에 맨 앞이나 맨 뒤에 한 글자 넣는 경우를 봤다. 단순하게 in으로 체크했다. 마지막으로는 토달기 방식 중 중간에 한 글자 넣은 경우인지 봤다. 이 부분이 젤 까다로운 것 같다. 나는 while을 이용해서 사전에..

문제 풀러 가기 풀이 🍅 | 한 마디로 하면 벽 부수고 이동하기 문제와 비슷하게 풀었다! 일단 최단 거리를 알아내는 문제니까 BFS로 풀어야 겠다고 생각했다. 그런데 특이한 것은 K번까지 말의 움직임처럼 움직일 수 있다는 것이다. 벽도 있으니까,, 무조건 K번 말의 움직임을 다 쓴다고 최소 동작으로 목적지까지 가는 것도 아니고.. 어쩌면 0번 말처럼 움직였을 때가 최소 동작일 수도 있을 것이다. 그래서 몇 번 말처럼 움직였는지를 고려해서 visit 체크를 3차원 리스트로 만들었다. K는 최대 30이니까 괜찮다 ! 나머지는 일반적인 BFS처럼 하면 된다. 코드 🖥 import sys from collections import deque input = sys.stdin.readline dx, dy = [0,..

[문제 보러 가기](https://www.acmicpc.net/problem/14940 평범한 BFS 문제였다. visited를 만들어서 방문 체크 겸, 거리 체크를 했다. 처음에는 '원래 갈 수 없는 땅인 위치는 0으로 출력'해야 하는데, 원래 갈 수 없는 땅이고 도달할 수 없는 위치면 -1로 출력해서 틀렸다. 그리고 i, j 오타가 나서 틀리다가 맞았다..! i, j.. 비슷하게 생겨서 주의해야 겠다. import collections import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] n, m = MIIS() a..

문제 보러 가기 많이 틀리다가 맞았다!!! 틀렸던 이유 🙆‍♀️ 시작 정점 1에서 시작하지 않는 경우도 들어올 수도 있는 것을 체크하지 않았다. 단순히 깊이가 같은 것만 체크하면 안된다. 진짜 큐처럼, 순서도 고려해야 한다. 2에 대해서 좀 더 설명하겠다. 처음에는 깊이만 같으면 다 되는 줄 알았다..! 그래서 딕셔너리를 이용해서 각 깊이 별로 자식을 저장했다. 깊이 1일 때: 1 깊이 2일 때 : 2, 3, 4 깊이 3일 때: 5, 6, 7 입력으로 주어진 BFS 방문 순서를, 각 깊이에 있는 요소들의 길이만큼씩 잘라서 둘다 set으로 만들었다. 두 set이 같은지 판단했다. 이렇게 했더니 50%정도에서 틀렸다. 만약에 1-> 3-> 4-> 2가 들어왔으면, 3의 자식들, 4의 자식들, 2의 자식들 순..

문제로 가기~ BFS로 풀었다. 쭉~ 보면서 아직 방문 안한 곳이면 bfs로 상하좌우 4방향을 본다. 출발한 곳의 색깔과 같으면 개수를 더한다. 그래서 몇 명의 병사가 뭉쳐있는지 세고, 해당하는 팀에 힘(뭉친 수의 제곱!)을 더한다. 이미 센 병사는 또 세면 안 되니까 방문 체크 import collections import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(list(input().strip()) for _ in range(M)) dir_x, dir_y = [0, 0, -1, 1], [-1, 1, 0, 0] def bfs(i, j, color): cnt = 1 q = collections.deque() v..

문제로 가기! 처음에는 어떻게 풀지 감도 잡히지 않았다. 문제 분류가 BFS라는데,, 이게 왜 BFS인지... 뭔가 수학적인 개념이나 그리디로 접근해야 하는 거 아닌가..? 하는 생각도 들었다. 그러다 스터디에서 다른 분의 설명을 듣고 나서 풀었다! BFS로 풀었다. 매번 K개 뒤집기를 해야 하는데, 이때 뒷면으로 뒤집어진 동전을 0~K개를 뒤집었을 때 어떻게 되는지 본다. 만약에 지금 뒷면인 동전이 5개인데, 7개 뒤집는 것은 말이 안되니까 그런 경우는 제외하고! 가능한 경우를 봤을 때, N개 동전 모두 뒷면이라면 그때까지 K-뒤집기를 한 횟수를 리턴하면 된다. 그게 아니라면, deque에 그 상태에서 뒷면인 동전 개수와 그때까지 뒤집기 횟수를 넣어주었다. visited 체크를 한 후에 deque에 넣..