5회차 후기
스택의 활용과 BFS 복습을 진행했다.
BFS는 저번주에 분명 익숙해졌다고 생각했지만, 일주일만에 다시 푸니까 조금 허술해진 스스로를 발견할 수 있었다. 계속 능숙하게 풀이하기 위해서 반복학습을 강화해야겠다.
괄호의 값에서 연산 방법을 발견하여 정의하는 것은 그렇게 어렵지 않았으나, 구현 방법이 어색해서 조금 오래 걸렸다. 그러나 생각한대로 풀어냈다. 발전해야 할 점은 생각한 것이 어색한 방법이더라도 확신이 있다면 구현을 꼼꼼히 차근차근 밟아가면 결국 풀어낼 수 있다는 것이다.
불
import java.util.*;
import java.io.*;
public class Main{
public static int[][] map;
public static int R;
public static int C;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
R = Integer.parseInt(line[0]);
C = Integer.parseInt(line[1]);
// J는 9
// F는 4
// #는 1
// .는 0
map = new int[R][C];
int[][] jihoonMap = new int[R][C];
Queue<int[]> fire = new LinkedList<>();
Queue<int[]> jihoon = new LinkedList<>();
for(int i=0; i<R; i++){
String input = br.readLine();
for(int j=0; j<C; j++){
char ch = input.charAt(j);
switch(ch){
case '#':
map[i][j] = -1;
jihoonMap[i][j] = -1; break;
case 'J':
map[i][j] = -9;
jihoonMap[i][j] = -9;
jihoon.add(new int[]{i, j}); break;
case 'F':
map[i][j] = -4;
jihoonMap[i][j] = -4;
fire.add(new int[]{i, j}); break;
case '.':
jihoonMap[i][j] = 0;
map[i][j] = 0; break;
}
}
}
// 지훈이는 불을 얼마나 빨리 탈출 가능?
// 불은 퍼진다!
// 불 퍼지는 걸 피하는 길로 가야할텐데!
// - 불은 지훈이를 덮칠 수 있다 (반면 지훈이가 불에 뛰어들면 자살행위지)
// - 지훈이가 불이 퍼질 위치로 가는 건 안된다 (즉 불을 먼저 퍼뜨린 뒤 지훈이를 퍼뜨리자)
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
int x, y;
int x_, y_;
int min = 1000*1000;
while(!jihoon.isEmpty()){
//불 (큐에 있는 불을 모두 poll해봐야 함)
ArrayList<int[]> tmp = new ArrayList<>();
while(!fire.isEmpty()){
int[] F = fire.poll(); // 아까 불난 자리
x = F[1]; y = F[0];
for(int i=0; i<4; i++){
x_ = x + dx[i];
y_ = y + dy[i];
if(x_<0||y_<0||y_>=R||x_>=C||map[y_][x_]==-1||map[y_][x_]==-4)
continue;
map[y_][x_] = -4;
tmp.add(new int[]{y_, x_});
}
}
for(int[] f : tmp){
fire.add(f);
}
// 지훈 (큐에 있는 지훈을 모두 poll해봐야 함)
tmp = new ArrayList<>();
while(!jihoon.isEmpty()){
// 지훈 현위치
int[] J = jihoon.poll();
int jX = J[1];
int jY = J[0];
int val = jihoonMap[jY][jX];
if(val == -9){
val = 0;
}
// 현위치 체크도 해야 함(탈출상태인지)
if(jX==0 || jX==C-1 || jY==0 || jY==R-1){
if(jihoonMap[jY][jX] == -9){
min = 0;
System.out.println(min+1); return;
}
else if(jihoonMap[jY][jX]!=-4 && jihoonMap[jY][jX]!=-1){
if(jihoonMap[jY][jX] < min)
min = jihoonMap[jY][jX];
}
}
for(int i=0; i<4; i++){
x_ = jX + dx[i]; y_ = jY + dy[i];
if(x_<0||y_<0||y_>=R||x_>=C||map[y_][x_]==-1||map[y_][x_]==-4)
continue;
// 갔던 곳을 되돌아가는 수는 없을까? 없다고 가정하고 일단 해보자.
if(map[y_][x_]==0){
tmp.add(new int[]{y_, x_});
jihoonMap[y_][x_] = val + 1;
map[y_][x_] = val + 1;
}
}
}
for(int[] j : tmp){
jihoon.add(j);
}
}
if(min<1000*1000)
System.out.println(min + 1);
else
System.out.println("IMPOSSIBLE");
}
}
괄호의 값
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split("");
// 뭔가 컴파일러랑 비슷한 느낌이다
// (()[[]])([])
// '깊게'들어가보는 것이 필요할듯하다
// (가 열린개수만큼 닫혔는가?
// [가 열린개수만큼 닫혔는가?
// 문제는 이제 연산을 하는 것인데
// 차근차근 생각해보니 이런 구조로 풀 수 있었음
Stack<String> stack = new Stack<>();
int[][] memo = new int[30][3];
int idx = 0;
int order = 0;
for(String data : line){
// System.out.println(stack);
if(data.equals("(")){
stack.push(data + " " + String.valueOf(order++));
} else if(data.equals("[")){
stack.push(data + " " + String.valueOf(order++));
} else {
if(stack.isEmpty()){
System.out.println(0); return;
}
// pop해서 확인하기
String[] str = stack.pop().split(" ");
String val = str[0];
int num = Integer.parseInt(str[1]);
if(data.equals(")")){
if(!val.equals("(")){
System.out.println(0); return;
}
memo[idx++] = new int[]{2, num, 0};
}
if(data.equals("]")){
if(!val.equals("[")){
System.out.println(0); return;
}
memo[idx++] = new int[]{3, num, 0};
}
if(stack.isEmpty()){
memo[idx-1][2] = 1;
}
}
}
if(!stack.isEmpty()){
System.out.println(0);
return;
}
int[][] terms = new int[30][3];
// for(int[] t_ : memo){
// if(t_[0]==0)
// break;
// System.out.println(Arrays.toString(t_));
// }
idx = 0;
int term_idx = 0;
int pre_order = -1;
int val = memo[idx][0];
while(val != 0){
order = memo[idx][1];
if(order > pre_order){
// 더하는 항
terms[term_idx++] = memo[idx];
}
else if(order < pre_order){
//이 항에서 1아 아닐 때까지 이전을 탐색
//그 항을 이전항에 곱하기 (본인보다 order가 높은 항에만!)
for(int i=idx-1; i>=0; i--){
if(memo[i][2]==1)
break;
if(order > memo[i][1])
continue;
memo[i][0] *= memo[idx][0];
}
}
pre_order = memo[idx][1];
val = memo[++idx][0];
}
int sum = 0;
for(int[] tm : terms){
if(tm[0]==0) break;
sum += tm[0];
}
System.out.println(sum);
}
}반응형
