BOJ.2931번.가스관

 

BFS로 양끝에서 탐색하고, 가스파이프가 끝나는 지점을 정한다. 정한 지점에서 어떤 파이프가 적절한지를 골라넣으면 된다.

Java, Python 두가지 모두 풀어보았다.

2931번: 가스관

in Java

import java.util.*;
import java.io.*;

class BOJ2931gaspipe {
    static int r, c, my, mx, zy, zx, fy, fx;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static char[][] europe;
    static boolean[][] check;
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        europe = new char[r][c];
        check = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < c; j++) {
                europe[i][j] = tmp.charAt(j);
                if (europe[i][j] == 'M') {
                    my = i;
                    mx = j;
                } else if (europe[i][j] == 'Z') {
                    zy = i;
                    zx = j;
                }
            }
        }
        bfs(my, mx, new int[] { 0, 1, 2, 3 });
        bfs(zy, zx, new int[] { 0, 1, 2, 3 });

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (europe[i][j] != '.' && !check[i][j]) { // 섬
                    bfs(i, j, direction(europe[i][j]));
                }
            }
        }
        Collections.sort(ans);
        // System.out.println(ans.toString());
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        char[] samples = new char[] { '|', '-', '+', '1', '2', '3', '4' };
        for (char c : samples) {
            if (Arrays.equals(res, direction(c))) {
                System.out.println((fy + 1) + " " + (fx + 1) + " " + c);
            }
        }
    }

    private static void bfs(int y, int x, int[] dir) throws Exception {
        Queue<Pos> q = new LinkedList<Pos>();
        q.add(new Pos(y, x, dir));
        check[y][x] = true;
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            int oy = cur.y;
            int ox = cur.x;
            int[] odir = cur.dir;

            for (int d : odir) {
                int ny = oy + dy[d];
                int nx = ox + dx[d];
                int nd = (d < 2) ? (d + 1) % 2 : (d + 1) % 2 + 2;
                if (checkBound(ny, nx) && !check[ny][nx]) {
                    if (europe[ny][nx] != '.') {
                        check[ny][nx] = true;
                        q.add(new Pos(ny, nx, direction(europe[ny][nx])));
                    } else {
                        if (europe[oy][ox] == 'M' || europe[oy][ox] == 'Z') {
                            continue;
                        }
                        if (fy == 0 && fx == 0) {
                            fy = ny;
                            fx = nx;
                        }
                        if (!ans.contains(nd)) {
                            ans.add(nd);
                        }
                    }
                }
            }
        }
    }

    private static int[] direction(char s) throws Exception {
        switch (s) {
            case '|':
                return new int[] { 0, 1 };
            case '-':
                return new int[] { 2, 3 };
            case '+':
            case 'M':
            case 'Z':
                return new int[] { 0, 1, 2, 3 };
            case '1':
                return new int[] { 1, 3 };
            case '2':
                return new int[] { 0, 3 };
            case '3':
                return new int[] { 0, 2 };
            case '4':
                return new int[] { 1, 2 };
            default:
                return null;
        }
    }

    private static boolean checkBound(int y, int x) throws Exception {
        return (y >= 0 && y < r && x >= 0 && x < c);
    }

    static class Pos {
        int y, x;
        int[] dir;

        public Pos(int y, int x, int[] dir) {
            this.y = y;
            this.x = x;
            this.dir = dir;
        }
    }
}

in Python

import sys
from collections import deque
input = sys.stdin.readline


def direction(s):
    if s == '|':
        return [0, 1]
    elif s == '-':
        return [2, 3]
    elif s == '+' or s == 'M' or s == 'Z':
        return [0, 1, 2, 3]
    elif s == '1':
        return [1, 3]
    elif s == '2':
        return [0, 3]
    elif s == '3':
        return [0, 2]
    elif s == '4':
        return [1, 2]


def bfs(y, x, dir):
    global final_y, final_x
    q = deque()
    q.append([y, x, dir])
    check[y][x] = True
    while q:
        oy, ox, odir = q.popleft()
        # print(oy, ox, odir)
        for d in odir:
            ny = oy + dy[d]
            nx = ox + dx[d]
            nd = (d+1) % 2 if d < 2 else (d+1) % 2+2
            # 방문한 적이 없을 때
            if 0 <= ny < r and 0 <= nx < c and not check[ny][nx]:
                if europe[ny][nx] != '.':  # 가스관이 있는자리라면
                    check[ny][nx] = True  # 방문체크해주고
                    # 그 가스관의 가능한 방향 넣어준다
                    q.append([ny, nx, direction(europe[ny][nx])])
                else:  # 가스관이 없는 빈칸이라면
                    if europe[oy][ox] == 'M' or europe[oy][ox] == 'Z':
                        continue
                    if final_y == 0 and final_x == 0:
                        final_y, final_x = ny, nx
                        # print(final_y, final_x)
                    if nd not in dir_candidate:
                        dir_candidate.append(nd)


r, c = map(int, input().split())
check = [[False]*(c) for _ in range(r)]

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

europe = []
for i in range(r):
    europe.append(list(input().strip()))
    for j in range(c):
        if europe[i][j] == 'M':
            my, mx = i, j
        elif europe[i][j] == 'Z':
            zy, zx = i, j
            # print(europe)
# print(my, mx, zy, zx)
dir_candidate, final_y, final_x = [], 0, 0
bfs(my, mx, [0, 1, 2, 3])
bfs(zy, zx, [0, 1, 2, 3])

# print(f'중간점검 {dir_candidate}, {final_y}, {final_x}')

for i in range(r):
    for j in range(c):
        if europe[i][j] != '.' and not check[i][j]:
            bfs(i, j, direction(europe[i][j]))

dir_candidate.sort()

# print(f'최종점검 {dir_candidate}, {final_y}, {final_x}')

samples = ['|', '-', '+', '1', '2', '3', '4']
for s in samples:
    if dir_candidate == direction(s):
        print(final_y+1, final_x+1, s)