문제#
- 링크로 대체
풀이 및 주저리..
수업 도중 풀어본 문제중 하나로 좀 많은 충격을 준 문제이다. 문제를 처음봤을때 2차원 배열에서의 마름모를 어떻게 구할지를 크게 고민했던 것 같다. 고민 보다는 겁을 먹었던 것 같다. 너무 어려운 시뮬레이션 문제들을 자주 봤던 탓인지 마름모의 테두리를 어떻게 구하지를 계속해서 고민했던 것 같다. 결국 아직 수업에서 배우지 않은 BFS 를 활용해서 문제를 어렵게어렵게 풀었고 풀고 나서 풀이를 들었을 때 지금 내가 너무 시야가 좁다는 것을 알게 되었다.
그냥 마름모 별찍기를 하면 되는 간단한 문제였던 것이다. 심지어 구글링 조금만 하면 한두줄로 끝을 낼 수 있는 문제.. 과거에 게리멘더링 4를 풀지 못했던 것이 생각나기도 했고.. 지금 풀면 뭔가 풀 수도 있을 것 같다는 생각을 했다. 쉬운 문제를 이렇게 어렵게 푸는건 시험에서는 정말 있어서는 안되는 일이기 때문에 지금 내가 문제가 있는 건가 라는 생각을 좀 많이 했던 것 같다. 처음 공부를 시작할때의 열정보다는 확실히 많이 떨어져있다고 생각이 들었고 안주하고 있는 것은 아닌가 고민을 들게 만들어준 문제였다.
먼저, 근래에 풀고 있는 대부분의 문제를 비슷하게 풀고 있다는 것이다. 범위를 체크하고 거기에 해당하는 반복을 돌리면서 모든걸 해결하려고 하니 코드가 엄청나게 길어지게 되었다. 싸피 수업을 듣는 다른 사람들의 코드를 보고 느낀점이 상당히 많았고 너무 내 스타일(이게 외워서 치는거랑 비슷한 것 같다) 를 고수하지 않고 이걸 어떻게하면 좀 더 깔끔하게 풀 수 있을까를 고민해봐야겠다.
참고로 밑에 solve가 반 친구가 푼 방법 위에가 내가 푼 방법이다. 차이가 상당하고 내 코드는 풀다보면 헷갈릴 수 있는 확률이 높다.
코드
package ssafy.swexpert.d3;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Solution_2805 {
static final int[][] dir = { { -1, 1 }, { 1, 1 }, { 1, -1 }, { -1, -1 } };
static final int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int iT = Integer.parseInt(br.readLine());
for (int t = 1; t <= iT; t++) {
int N = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
boolean[][] rangeMap = new boolean[N][N];
for (int i = 0; i < N; i++) {
String oneLine = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = Character.getNumericValue(oneLine.charAt(j));
}
}
drawRange(rangeMap, N);
int answer = getAnswer(map, rangeMap);
System.out.println("#" + t + " " + answer);
}
}
private static int getAnswer(int[][] map, boolean[][] rangeMap) {
int answer = 0;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (rangeMap[i][j])
answer += map[i][j];
}
}
return answer;
}
private static void drawRange(boolean[][] rangeMap, int n) {
if (n == 1) {
rangeMap[0][0] = true;
return;
}
int x = n / 2;
int y = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < n / 2; j++) {
rangeMap[x + dir[i][0]][y + dir[i][1]] = true;
x += dir[i][0];
y += dir[i][1];
}
}
Queue<Integer> que = new LinkedList<>();
que.add(n / 2);
que.add(n / 2);
rangeMap[n / 2][n / 2] = true;
while (!que.isEmpty()) {
x = que.poll();
y = que.poll();
for (int i = 0; i < 4; i++) {
int mX = x + dx[i];
int mY = y + dy[i];
if (!rangeMap[mX][mY]) {
que.add(mX);
que.add(mY);
rangeMap[mX][mY] = true;
}
}
}
}
}기억에 남길 것!
- 외워서 알고리즘을 풀지말자2
- 처음에는 문제를 단순하게 생각해보는 것도 좋다.