Coder's Cattitude

📌 풀이 문제 자체는 어렵지 않았지만, 좌표를 행렬에 대입해서 생각할 때 오류를 조금 범했다. 가로의 길이가 M이고 세로의 길이가 N인 직사각형의 경우 좌표가 (x,y)라면, 행렬의 경우 matrix[y][x]와 같다. 좌표를 행렬에 대입해서 생각하면, x좌표는 열, y좌표는 행이 되는 것이다. 그래서 아래 그림처럼 N행 M열인 행렬 (가로 M 세로 N인 행렬)을 transpose 시켜서, M행 N열인 행렬로 바꿔서 풀었다. 이렇게 행렬을 바꿔놓으면 별 문제 없이 코드가 작동하는 것을 알 수 있다. 🔑 python 코드 # 유기농 배추 import sys from collections import deque input = sys.stdin.readline T = int(input()) def bfs(x,..

📌 풀이 이 문제는 어디서부터 시작해야하는 지 나와있지 않기 때문에, NxN을 모두 다 돌 수 있도록 BFS로 풀었다. DFS로 풀어도 풀리지만 BFS로 푼 문제가 몇 개 없어서 그냥 BFS로 풀어봤다. 시간이 나면 DFS로도 풀어봐야겠다. 그래프에서 상하좌우로 이동할건데, 0행, N-1행, 0열, N-1열만 다르게 조건을 주기 싫어서 padding을 넣었다. 그래서 NxN가 아니라 (N+2)x(N+2) 그래프리고 패딩값들은 모두 0으로 채워넣었다. 문제에서 주어지는 값들을 graph에 저장하고, 만약 1이라면 BFS를 실시하고, 아니면 그냥 넘어가도록 했다. bfs에서도, 현재 위치에서 갈 수 있는 좌표들을 queue에 넣어놓고, queue가 다 빌 때까지 탐색을 진행하여 단지에 속하는 집의 수를 re..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 너무 어렵게 생각했던 것 같다. 그냥 진짜 그래프 문제였다. 신기하게 풀어본다고 이것저것 시도하다 그냥 DFS로 풀었다. 문제에서 주어지는 간선들을 graph에 저장하고, DFS로 1부터 시작해서 재귀함수를 써가며 풀었다. parents = [0, 0, 0, 0, 0, 0, 0, 0] graph에 저장된 것들을 적어본다면 graph[1] = [6, 4] graph[2] = [4] graph[3] = [6, 5] graph[4] = [1, 2, 7] graph[5] = [3] graph[6] = [1,3] graph[7] = [4] 이다. dfs(1)을 해주면 graph[1]에서 첫번째 값인 6의 parents가 0인지 확인하고, parents[6]을 1..