[SWEA] D4. Ladder1 Python, Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

 

 

1. 해결방법

위 그림을 보면 위에서 아래로 연결되는 사다리 길을 찾는 문제이다.

여기서 포인트는 아래로 가다가 좌 또는 우로 갈 수 있는 경로가 생긴다면 반드시 반드시 좌 또는 우로 가야한다. 좌 또는 우가 같은 위치에서 생길 순 없다.

문제대로 위에서 아래로 사다리 길을 찾는 탐색을 시작한다면 많은 경우의 수가 생길 것이다.
이를 해결하고자, 정해진 출구 2인 아래 위치에서 위로 이동하면 한 번의 경우의 수로 사다리 경로를 찾을 수 있다.

1. while 문을 이용해서 y 인덱스를 점차 위로 이동한다.
2. if 문의 순서를 이용해서 좌 또는 우로 갈 수 있다면 x 인덱스의 위치를 변경한다,
3. 지나간 자리는 재 방문할 수 있으니 방문체크를 한다.
4. y 가 0 일 때 즉, 맨 위쪽에 있을 때 x 위치를 구한다.

 

 

2. 정답코드 Java

package SWEA;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;

        for(int test_case = 1; test_case <= T; test_case++) {


            int N = Integer.parseInt(br.readLine());

            int[][] maps = new int [100][100];
            boolean[][] chk = new boolean[100][100];

            for (int i = 0; i < 100; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 100; j++) {
                    maps[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < 100; i++) {
                if (maps[99][i] == 2) {
                    int y = 99;
                    int x = i;
                    boolean isFlag = false;
                    while (true) {
                        if (x - 1 >= 0) {
                            if (!chk[y][x - 1]) {
                                if (maps[y][x - 1] == 1) {
                                    chk[y][x - 1] = true;
                                    x -= 1;
                                }
                            }
                        }
                        if (x + 1 < 100) {
                            if (!chk[y][x + 1]) {
                                if (maps[y][x + 1] == 1) {
                                    chk[y][x + 1] = true;
                                    x += 1;
                                }
                            }
                        }
                        if (maps[y - 1][x] == 1) {
                            chk[y - 1][x] = true;
                            y -= 1;
                        }

                        if (y == 0 && maps[y][x] == 1) {
                            System.out.println("#" + test_case + " " + x);
                            isFlag = true;
                            break;
                        }
                    }
                    if (isFlag) break;
                }
            }
        }
    }
}

 

 

3. 정답코드 Python

import sys
input = sys.stdin.read

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    maps = [list(map(int, input().split())) for _ in range(100)]
    chk = [[False] * 100 for _ in range(100)]


    n = 99
    isFlag = False
    for i in range(100):
        if maps[n][i] == 2:
            x = i
            while True:
                if 0 <= x - 1 < 100:
                    if chk[n][x - 1] == False:
                        if maps[n][x - 1] == 1:
                            chk[n][x - 1] = True
                            x -= 1
                if 0 <= x + 1 < 100:
                    if chk[n][x + 1] == False:
                        if maps[n][x + 1] == 1:
                            chk[n][x + 1] = True
                            x += 1

                if maps[n - 1][x] == 1:
                    chk[n - 1][x] = True
                    n -= 1

                if n == 0 and maps[n][x] == 1:
                    isFlag = True
                    print(f'#{test_case} {x}')
                    break
        if isFlag:
            break