본 포스팅은 필자가 한참 헤매서 작성하며, 혹여라도 길 잃은 영혼이 이 포스팅을 보고 해결되었으면 좋겠습니다.

저는 Intellij IDE 를 사용하며, 스프링 레거시 프로젝트를 진행하면서 공부하던 와중에 테스트 케이스를 작성 중에 @Before가 동작하지 않는 문제점입니다.

@Before 어노테이션이 동작하기 위해서는 기본적으로 필요한 @Test 어노테이션은 

1.  import org.junit.Test;

자동으로 import된 @Test 어노테이션은 ?

2. import org.junit.jupiter.api.Test;

따라서 Test import 문을 1번으로 변경해주시면 @Before가 잘 동작할 것입니다.

"나를 사랑하게"

참 많은 책들이 자존감에 대해서 다룬다. 그만큼 스스로를 사랑하는 것, 자존감을 높히는 것은 꾸준하게 중요시되어 왔다는 이야기다. 한국의 정서를 생각해보면, 나보다 남을 배려하는 것에 대한 중요성을 더 강조하다. 자연스럽게, 그러한 분위기 속에서 커 온 사람들은 자신을 낮추더라도 남을 배려한다. 

미국에서 1년동안 살면서 못해도 500명 이상의 다양한 사람들을 만났었다. 이 때 많은 사람들이 자신이 뚱뚱하다고, 자신이 못생겼다고, 자신이 공부를 못한다고, 부족하더라도 스스로를 사랑하는 사람들이 과반수이상이었다. 하지만, 한국에 와서 많은 사람들과 이야기를 하면서 충분히 매력적이고, 자존감을 가져도 충분한 사람들이 스스로를 낮추고, 비판하며 스스로를 사랑하는 않는 경우가 많았다. 

나를 사랑하지 못하는데, 누굴 사랑할 수 있을까? 그러니 나에게 집중하고, 자신을 가장 중요하게 생각하고 소중하게 여기자. 남에게 나의 가치를 인정받으려고 하지 않고, 내가 내 가치를 인정하고 귀하고 멋지다고 생각하자. 그럼 나의 여유로움이 넘쳐나며, 남들에게 자연스럽게 흘러나갈 것이다.

"본인의 가치는 본인이 만드는 것"

 말이라는 것은 본인을 대변한다. 내가 말을 거칠게 한다면 나는 거친 사람이 되고, 부드럽게 한다면 부드러운 사람이며, 품위있게 말한다면 품위있는 사람이 된다. 이처럼 말이라는 것은 나 자신의 대표하는 브랜드이다. 내가 아무리 마음이 여리다한들 입 밖으로 내뱉는 말이 거칠다면, 다른 사람들의 눈에는 거칠게 보일뿐이다. 

모든 관계는 말로부터 시작한다. 세상에 둘러보면 말없이 시작된 관계는 사실 찾아보기 힘들다. 따라서 이러한 관계에서 가장 큰 부분을 차지하는 것은 말이 아닌가 생각한다. 그래서 말을 할 때는 단순히 내 생각과 입장만 전달하는 것에 초점을 맞추는 것이 아니라 상대의 마음과 권리에 위협이 가지 않도록 현명하게 이야기하는 것이 중요하다.

말의 힘은 강력하다. 내가 가질수 있는 능력 중에 가장 강력한 능력이라 생각한다. 따라서, 늘 감사함을 표하고, 예쁜 말을 함으로써 스스로를 명품으로 만들었으면 한다. 

나는 나를 위해 예쁜 말을 한다.

누구나 존중받고자 한다. 내 노력을 인정받고자 하고, 무리에서 괜찮은 사람으로 보이고자 한다. 이런 본능은 많은 사람들에게 있는 본능이다. 따라서 쟁취하기 위한 싸움을 한다. 이 과정에서 다칠수도 있고, 다치게 할 수도 있다. 하지만 곰곰히 생각해보면 나의 가치를 인정받는 것은 다른 사람에 의해 검증될 수 없다. 다른 사람이 백날 너는 너는 소중하다 소중한다한들 내가 나를 소중히 여기지 않는다면 나는 스스로 이미 소중하지 않은 사람이라는 결론을 내렸기 때문이다. 

그러니 스스로에게 귀를 기울여 "나는 소중한 사람이다" 를 하루에 한번씩 이야기해주자. 또 내가 소중한 사람이라면 나를 위해 예쁜 말을 하자. 말이라는 것은 내뱉는 순간부터 부메랑이 던져진 것이다. 내가 이쁜 말을 내뱉았다면 부메랑은 이쁜 부메랑으로 날라갈 것이다. 하지만 칼같은 말을 뱉는다면 나에게 칼이 되어 돌아온다. 그러니 말하기 전에 내가 지금 할 이 말이 다시 나에게 돌아올 때, 내가 잡을수 있는 부메랑인지 아닌지 또 생각하고 생각해야 한다.

"오늘도 잘하고 있어"

마음을 울리는 책 이름 : 예쁘게 말을 하니 좋은 사람들이 왔다.

취업 준비를 하며 방에서 갇혀지내며 전공 서적만 본 게 어연 3개월은 된 것 같다. 생각보다 바쁜 삶에 치여서 숨쉴 공간이 필요했던 나는 인천 영종도에 있는 친구집으로 잠시 휴가아닌 휴가, 장소의 변화를 주고자 왔고, 마침 딱! 친구의 책장에 보인 책 한권이 있었다.

"예쁘게 말을 하니 좋은 사람들이 왔다" 

가슴에 책 제목이 꿈틀하고 들어온 느낌이였다. 그래서 친구 집에 있으면서 꼭 읽어야겠다는 다짐이 들었고, 오늘 공부에 집중이 잘 되지않던 찰나에 이 책을 읽어보자 내 책상에 가져왔다. 책을 펴자마자 좋은 느낌이 몽글몽글 나를 감싸는 느낌이 들었고, 책을 내려놓을 틈없이 집중해서 읽게 되었다. 하나하나 모든 말들이 나에게 변화를 주는 느낌이였다. 4시간동안의 짧다면 짧고 길다면 긴 여정을 끝내고 책을 내려놓았을때 아! 다른 사람들도 읽었으면 좋겠다. 이 책이 나에게 주는 좋은 메시지가 많은 사람들에게 전파됐으면 좋겠다.

많은 사람들이 이 책을 보고 세상이 아름다워지면 얼마나 좋을까 하는 마음이 들었고, 난생 처음 자발적인 독후감을 써본다.

이 책의 저자 '심희정'님은 기자라는 직업을 가지고 있다. 지금 많은 기사들을 보면 상당히 자극적이고 공격적으로 기사를 작성하기에, 나도 모르게 기자라는 직업에 대해서 부드러운 언행보다 날카롭고 공격적인 부분이 많다는 생각을 가지고 있었는데, 이러한 직업을 가지고도 이러한 품성과 언행을 가지게 된 심희정님에게 큰 존경심이 든다. 

본론으로 들어가서, 책을 읽으면서 인상을 받은 몇가지 부분에 대해서 이야기해보도록 하겠다.

이 책은 예쁜 말을 어떻게 할 것인가에 대한 부분보다 나를 "어떻게 Better Person이 되게 하는가!"에  좀 더 초점이 맞춰져 있던 것 같다. 우리는 현재 칭찬에 인색한 시대에 살고 있음에도 불구하고 사실 예쁜 말을 하는 것은 어렵지 않다. 한번 더 생각하고 말을 하면 되지 않는가?

하지만 이 책에서는 단순히 예쁜 말을 하는 것보다, 나를 어떻게 변화시켜야 하는가에 초점이 맞춰져 있기에, 더 예쁜 말을 하기 위해서 내가 가져야 하는 심성이 무엇인가? 내가 사람을 어떻게 관심해야 하는가? 에 대한 내용에 대해서 많은 부분 저자의 경험담과 충고가 담겨있다.

마음을 담은 칭찬을 하자

칭찬이라는 부분에 대해서 이야기해보자. 이 책을 읽으면서 나 스스로 내가 칭찬을 하는 사람인가 되돌아봤을때 전혀 아니였다. 되려 좀 더 객관적인 부분을 보고자 했고, 타인이 잘하는 부분이 분명히 있음에도 불구하고 못하는 부분에 대해서만 이야기하였다. 또 생각해보면, 취업을 준비하는 과정에서 많은 프로젝트에서 팀장을 했었는데, 프로젝트 과정에서 팀원들의 역량을 이끌어내는게 사실 매번 힘들었다. 왜 힘들었을까? 사실 나는 그들의 장점을 이끌어내려고 노력했는가에 대한 질문을 받는다면 아니요.. 라는 말을 할 것 같다. 팀원들을 관심하고 진실로 믿음을 가지고 그들의 장점을 이해하려고 주의깊게 봤다면 충분히 화이팅 넘치는 프로젝트를 했을것이고, 좋은 결과를 얻었을 것이라 생각한다. 

듣는 태도의 중요성

사실 이미 많은 대화 관련 책들에서 가장 많이 다루는 주제는 듣는 태도가 아닐까 한다. 자기 계발서로 여러 책들을 읽어보았을때 듣기라는 부분이 사실 말하기보다 더 중요하다는 것은 이미 알고 있었다. 알고 있음에도 불구하고 나를 되돌아보면 대화에서 항상 내가 말이 많았던 편이다. 이 뿐만 아니라 대화에서 내가 관심이 없는 내용이 나오면 그들이 말하고 있음에도 불구하고 불성실한 불량학생처럼 듣고, 주제를 돌려버리기 일수였다. 아 정말 최악이다. 이 책은 상대방이 이야기할때 진심이라는 부분을 매우 강조한다. 진심이 없는 맞장구는 네거티브 바디 제스쳐로 하는것만 못하다. 아주 간단한 "아 정말?" "아 진짜?" "처음들어" "대박" 이러한 맞장구도 진심이 담긴다면 상대방을 신나게 하고 당신의 대화를 행복한 시간으로 만들어줄 것이라는 내용을 담고 있었다. 

나를 관심하자

사실 모든 건강한 언행은 나의 건강한 마음에서 나온다. 내 스스로가 건강한 사람이어야 예쁜 말, 또 타인에게 진심으로 관심을 가지며 대화를 할 수 있다는 것이다. 먼저 스스로를 사랑하고 자존감을 높히는 것이 좋은 대화의 첫걸음이라는 것을 이야기하는데 나는 깊이 공감한다. 운동을 하여 체력을 기르고, 내가 좋아하는 몸을 만들고 옷을 사고 옷을 입었을 때 스스로가 느끼는 만족감이 높았을 때를 생각해보면, 나는 꽤 예쁜 말들을 했던 것 같다.

마지막으로, 4년만에 전공서적 이외의 책을 읽어보는데, 한 달에 두 권은 꼭 다른 책들을 읽어야겠다는 생각이 들었다. 먼가 책을 읽는 목적성을 두기보다 이러한 자극적인 세상의 컨텐츠에서 아름다운 글들을 읽는다는 것은 나에게 하나의 힐링이 될 것이다 라는 믿음으로 자리 잡았다.

book.interpark.com/product/BookDisplay.do?_method=detail&sc.shopNo=0000400000&sc.prdNo=320884331&sc.saNo=003002001&bid1=search&bid2=product&bid3=title&bid4=001

www.acmicpc.net/problem/11066

DP 문제는 쉬워도 점화식 세우는 부분에서 항상 어려움을 겪는다.

알고나면 별거 아닌데, 막상 접하면 어렵다.

이 블로그까지 찾아왔다는 이야기는 이 전에 이미 풀이를 작성한 블로그에서 보여주는 풀이가 이해하는 부분에 있어서 헤매다 왔을것이라 생각한다. 한번 잘 설명해보겠다.

파일 합치기는 메모이제이션 문제임으로 점화식을 세울 필요성이 있다.

따라서 먼저 식에 대한 정의가 필요하다.

dp[ i ][ j ] 를 무엇이라 정의할 것인가?

dp[ i ][ j ]는 i번 페이지부터 j번 페이지까지 페이지를 합한 최솟값이라 정의하겠다.

점화식?

우선적으로 dp[ i ][ i ] 일때 생각해보자. i페이지부터 i페이지까지의 합은 즉 i번째 페이지의 값인 novel[ i ] 가 될 것이다.

그럼 dp[ i ][ i + 1] 은?

dp[ i ][ i + 1 ]은 novel[ i ] + novel[ i + 1 ] 이 될것이다.

그럼 dp[ i ][ i + 2]는 어떻게 될 것이냐? 

dp[i][i] + dp[i+1][i+2] + (novel[i]  + novel[i + 1] + novel[i + 2]) , dp[i][i+1] + dp[i + 2][i + 2] + (novel[i] + novel[i + 1] + novel[i + 2]) 값중에 작은 값이 되지 않겠는가?

이를 다시 점화식으로 풀어보자.

dp[i][j] = divide가 i + 1 부터 시작해서 j - 1까지 순회하면서 비교했을때 dp[i][i + divide] + dp[divide + 1][j] + sum(i부터 j까지 부분합) 이 될 것이다.

그리고 페이지를 묶어내야 함으로 두장씩 묶고, 세장씩 묶는 과정들이 필요하다.

for 1장부터 n장까지 묶기 n <= k(몇장을 묶을것인가?
	for 1부터 k까지 from + n <= k  (어디부터 묶기 시작할것인가)
    		for 1부터 k까지 divide < from + n (범위가 주어졌을때 특정 지점으로 나눠서 최대값 구하기)

그럼 위와 같은 3차원 반복문이 나올것이다. 이를 코드화하면 

for (int n = 1; n <= k; n++) {
    for (int from = 1; from + n <= k; from++) {
        int to = from + n;
        dp[from][to] = Integer.MAX_VALUE;
        for (int divide = from; divide < to; divide++) {
            dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
        }
    }
}

위와 같이 된다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    public static void main(String[] args) throws Exception {
        int t;

        t = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < t; tc++) {
            int k;
            int[] novel;
            int[] sum;
            int[][] dp;

            k = Integer.parseInt(br.readLine());
            novel = new int[k + 1];
            dp = new int[k + 1][k + 1];
            sum = new int[k + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                novel[i] = Integer.parseInt(st.nextToken());
                sum[i] = sum[i - 1] + novel[i];
            }

            for (int n = 1; n <= k; n++) {
                for (int from = 1; from + n <= k; from++) {
                    int to = from + n;
                    dp[from][to] = Integer.MAX_VALUE;
                    for (int divide = from; divide < to; divide++) {
                        dp[from][to] = Math.min(dp[from][to], dp[from][divide] + dp[divide + 1][to] + sum[to] - sum[from - 1]);
                    }
                }
            }

            System.out.println(dp[1][k]);
        }

    }
    /**
     * memoization dp
     * 점화식
     * dp[i][j] = i부터 j장까지 합치는 비용
     * dp[i][i] = novel[i]
     * dp[i][i + 1] = novel[i] + novel[i+1]
     */

}

www.acmicpc.net/problem/6087

전형적인 백트래킹 문제다. 

문제의 요점은 탐색 + 백트래킹 장치를 거는 것이다.

여기서 백트래킹 장치라는 것은 레이저를 회전시키는 최소 횟수를 구하는 것이니, 회전이라는 것은 탐색하면서 방향을 트는 횟수가 최소가 되게 하면 된다는 것이다.

따라서 주어진 지도와 같은 크기의 turnCnt 배열을 생성한다.

탐색하는 과정에서 특정 위치 x, y에 도착하였을때 지금까지 방향을 몇 번 틀었나 체크를 해주게 되고, 이 방향 튼 횟수를 turnCnt[x][y]에 기록하면 된다.

글로 보면 이해가 안될것이다. 예제를 하나 들어보자.

예를 들어 아래와 같은 입력이 주어진다고 하자.

4 4
C.**
..**
....
...C

그리고 turnCnt 배열의 초기값은 최대값으로 해준다.

시작 위치는 왼쪽 상단 C 위치인 (0, 0) 부터 시작하여 도착 위치인 (3, 3)으로 이동하면서 체크해야 할 부분은 다음과 같다.

1, 4방향 탐색을 진행한다.

2. 다음 좌표에까지 방향 전환 횟수가 지금까지 오면서 꺽은 횟수보다 많거나 같으면 갱신하면서 재 탐색해준다.

3. 그렇지 않으면 이전으로 가서 다시 탐색한다.

[0, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[2147483647, 2, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 2147483647, 2147483647]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 2147483647, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 7, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 7, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 6, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 6, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 6, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 6, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 5, 6]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 5]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 5, 5]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 5, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 4, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 4, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 2, 4, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 4, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 4]

[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 3, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 3, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 3]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 3, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 2, 3]

[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 2, 2]

계속해서 백트래킹해주면서 탐색해주면 목적지에 최소 회전 값이 갱신되어 있을 것이다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    static final char EMPTY = '.';
    static final char WALL = '*';
    static final char C = 'C';
    static final int START = 0;
    static final int END = 1;
    static int w, h, idx;
    static char[][] map;
    static Point[] p;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        p = new Point[2];
        map = new char[h][w];
        visited = new boolean[h][w];
        turnCnt = new int[h][w];
        idx = 0;

        for (int i = 0; i < h; i++) {
            String line = br.readLine();
            for (int j = 0; j < w; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == C) {
                    p[idx++] = new Point(i, j);
                }
            }
            Arrays.fill(turnCnt[i], Integer.MAX_VALUE);
        }
        min = Integer.MAX_VALUE;
        visited[p[START].x][p[START].y] = true;
        dfs(p[START].x, p[START].y,-1, 0);

        System.out.println(turnCnt[p[END].x][p[END].y] - 1);
    }

    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static boolean[][] visited;
    static int[][] turnCnt;
    static int min;

    private static void printMap(int[][] map)
    {
        for (int i=0; i<map.length; i++){
            System.out.println(Arrays.toString(map[i]));
        }
        System.out.println();
    }

    private static void dfs(int x, int y, int exDir, int turn) {
        if (x == p[END].x && y == p[END].y) {
            turnCnt[x][y] = turn;
            return;
        }

        turnCnt[x][y] = turn;

//        printMap(turnCnt);
        for (int dir = 0; dir < 4; dir++) {
            int nx, ny;

            nx = x + dx[dir];
            ny = y + dy[dir];
            if (0 <= nx && nx < h && 0 <= ny && ny < w && !visited[nx][ny]
            && map[nx][ny] != WALL)
            {
//                System.out.println(nx+" "+ny);
//                System.out.println("dir : "+dir +" exDir : "+exDir+" turn : "+turn+" turnCnt[nx][ny] : "+turnCnt[nx][ny]);
                visited[nx][ny] = true;
                if (dir == exDir)
                {
                    if (turnCnt[nx][ny] >= turn)
                    {
                        dfs(nx, ny, dir, turn);
                    }
                }
                else
                {
                    if (turnCnt[nx][ny] >= turn + 1)
                    {
                        dfs(nx, ny, dir, turn + 1);
                    }
                }
                visited[nx][ny] = false;
            }

        }


    }


    public static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

www.acmicpc.net/problem/6549

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    public static void main(String[] args) throws Exception {

        while (true) {
            int n;
            long max;
            int[] histogram, left, right;

            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            histogram = new int[n];
            if (n == 0)
                break;
            for (int i = 0; i < n; i++) {
                histogram[i] = Integer.parseInt(st.nextToken());
            }
            left = getLeft(histogram, n);
            right = getRight(histogram, n);
            max = getMaxArea(left, right, histogram, n);
            System.out.println(max);
        }

    }

    private static long getMaxArea(int[] left, int[] right, int[] histogram, int n) {
        long max = Integer.MIN_VALUE;
        long cur;
        for (int i = 0; i < n; i++) {
            cur = (long) (right[i] - left[i] - 1) * histogram[i];
            max = Math.max(max, cur);
        }
        return (max);
    }

    private static int[] getRight(int[] histogram, int n) {
        int[] right = new int[n];
        Stack<Bar> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            if (stack.isEmpty() || stack.peek().height < histogram[i]) {
                right[i] = i + 1;
                stack.push(new Bar(histogram[i], i));
            } else {
                while (true) {
                    if (!stack.isEmpty() && stack.peek().height >= histogram[i])
                        stack.pop();
                    else {
                        right[i] = stack.isEmpty() ? n : stack.peek().idx;
                        stack.push(new Bar(histogram[i], i));
                        break;
                    }
                }
            }
        }
        return (right);
    }

    private static int[] getLeft(int[] histogram, int n) {

        int[] left = new int[n];
        Stack<Bar> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || stack.peek().height < histogram[i]) {
                left[i] = i - 1;
                stack.push(new Bar(histogram[i], i));
            } else {
                while (true) {
                    if (!stack.isEmpty() && stack.peek().height >= histogram[i])
                        stack.pop();
                    else {
                        left[i] = stack.isEmpty() ? -1 : stack.peek().idx;
                        stack.push(new Bar(histogram[i], i));
                        break;
                    }
                }
            }
        }
        return (left);
    }


    public static class Bar {
        int height, idx;

        public Bar(int height, int idx) {
            this.height = height;
            this.idx = idx;
        }
    }
}

새로운 유형의 문항이다. 문제 풀이법이 상당히 다양하나, 아래의 설명을 참고해서 문제를 풀었다. 이 문제에 대한 풀이를 여러군데서 찾아보았으나, 가장 이해가 잘 되고 명확한 풀이는 아래와 같다.

아래 풀이 내용을 참고하여 메인 로직을 작성했고, 풀고 나서 생각해보면 그렇게 어려운 문제는 아니였으나, 경험이 없었다면 실전에서도 풀지 못했을 것이다.

www.youtube.com/watch?v=v4OX1OTzma4